Сортировка битовых векторов

[ezus]

Добрый день.
что-то мозги заело.
Не могу придумать алгоритм сортировки битовых масок.

Проблема со сравнением 2 масок.

Каждый бит отражает наличие или отсутствие объекта с номером равным номеру бита (0-16).
Маска храниться в USHORT.

Сортировку надо выполнить как лексикографическую по возрастанию, т.е.

0х0009 > 0х0001:  1+4  > 1

но

0х0009 < 0х0006:  1+4 < 2+3

По возможности без циклов

Спасибо.

[darkelf]

У меня получилось что-то типа такого, правда с циклом:

Код: (C)

#include <stdio.h>

int num_of_bits16(unsigned short _arg)
{
    _arg = (_arg & 0x5555) + ((_arg >> 1) & 0x5555);
    _arg = (_arg & 0x3333) + ((_arg >> 2) & 0x3333);
    _arg = (_arg + (_arg >> 4)) & 0x0F0F;
    _arg = _arg + (_arg >> 8);

    return (int)(_arg) & 0x3F;
}

int cmp(unsigned short m1, unsigned short m2)
{ int c1, c2, i;

  c1 = num_of_bits16(m1);
  c2 = num_of_bits16(m2);

  if (c1 != c2)
    return c1 - c2;

  for (i = 0; i < 16; i++)
  { c1 = m1 & (1 << i);
    c2 = m2 & (1 << i);
    if (c1 != c2)
      return c2 - c1;
  }

  return 0;
}

int main(int argc, char* argv[])
{ unsigned short m1, m2;
  char* p;
  int r;

  if (argc > 2)
  { m1 = strtol(argv[1], &p, 16);
    m2 = strtol(argv[2], &p, 16);

    r = cmp(m1, m2);

    if (r == 0)
      p = "=";
    else
    if (r > 0)
      p = ">";
    else
      p = "<";

    printf("m1 %04x %s m2 %04x\n", m1, p, m2);
  }
  else
    printf("usage: %s <m1> <m2>\n", argv[0]);

  return 0;
}

Правда не уверен, что правильно понял лексикографическое сравнение битов.
Алгоритм подсчёта числа бит в слове взят отсюда.

[ezus]

Спасибо.
Похоже без цикла не обойтись.
Я хотел найти, что-нибудь типа подсчета единиц в байте одной командой - путем адресации к таблице из подготовленных заранее 256 количеств.

[darkelf]

Я хотел найти, что-нибудь типа подсчета единиц в байте одной командой - путем адресации к таблице из подготовленных заранее 256 количеств.

Если у Вас используется компилятор gcc, и более-менее новый процессор (с SSE4), то там есть поддержка специальной встроенной функции __builtin_popcount(), которая разворачивается в команду ассемблера popcnt, которая подсчитывает число единичных бит в 32-х разрядном слове.
В Microsoft-овских компиляторах есть что-то подобное: __popcnt16(), __popcnt(), __popcnt64() см. тут.

С таблицей - не уверен, что будет работать быстрее, да и элементов для 16-ти разрядного слова должно быть 65536, что потянет 128К памяти только на таблицу. В варианте с and-ами и сдвигами, конечно, команд побольше, но они не должны, вроде, сильно засорять кеш данных процессора. Плюс саму функцию подсчёт бит можно сделать inline.

[Aether]

Что-то немного непонятно: биты суммируются не просто количественно, а по позициям:
0x0009 = 1001 = 1+4, тогда тут простым суммированием числа битов, как бы, не прокатит, ведь суммирование даст 2, а надо 5?

[darkelf]

Что-то немного непонятно: биты суммируются не просто количественно, а по позициям:
0x0009 = 1001 = 1+4, тогда тут простым суммированием числа битов, как бы, не прокатит, ведь суммирование даст 2, а надо 5?

как я понял, т.к. это нужно для сортировки, то сначала сортируем по длинам битовых масок, а потом, для одинаковых длин - уже по значениям этих масок.

[Aether]

Всё упирается в сканирование строки битов с подсчётом суммы весов от каждого бита. Сканирование можно организовать через цикл, а можно его развернуть - 16 повторов не так уж и много.
darkelf прав, таблица в 8 бит, в данном случае, не подойдёт, как ни сравнивай. А таблица в 16бит уже намного весомее.
Если не секрет, Вы пишете программу для МК?

[Ochkarik]

может не в тему скажу...
была довольно старая книжка "Алгоритмические трюки для программистов
 Авторы: Генри С. (мл.) Уоррен". еще "тех" времен. там было нное количество алгоритмов подсчета бит, типа приведенной выше реализации "num_of_bits16"... и вообще много интересного.
главное - там были описана математика этих алгоритмов. попробуйте полистать - может пригодится.
PS или она по другому называлась... ща попробую найти. да вроде она. хотя не настолько старая оказалась, странно.

[ezus]

Я работаю с MS VS 6.0 (C++)
Клиенты самые разные, поэтому на специфику процессора ориентироваться не могу.

Я ввел вас в заблуждение своим плюсом.
Он означает только что в маске есть объекты с номерами 4 и 1, или 2 и 3.
Суммирование не помогает.

Под как-будто лексико-графической сортировкой я понимал аналогию с сортировкой текстов, где каждый номер - это буква в некоем алфавите. Т.е. сначала сортируем по первой букве(номеру), потом внутри по второй, и т.д.

Для масок - это будет: сначала по позиции первой единицы в маске, потом по второй, и т.д.

Все правы по поводу таблицы для USHORT. Она слишком большая, но я использую таблицу для 1 байта.
В этом случае вместо 1 команды получается:
- взять 1 байт
- получить значение из таблицы
- взять 2 байт сдвигом на 8
- получить значение из таблицы
- объединить полученные значения.
Всего 5 команд. Это быстрее цикла.

Этот подход я использую для других операций с масками. Например:
- подсчет единиц
- определение первого номера
- определение последнего номера
- ...

А вот для сортировки я не смог придумать такую таблицу.

[Aether]

Для правильного решения, часто, нужно правильно изложить задачу. Попробуем разобраться:
Дано:
  Есть некий массив из структур (0...N).
  Одно из полей структуры маска (mask - 16бит факт, для примеров 4бит).
  Само поле маски образуется маркерами объектов, например:
  Объект А имеет маркер ххх1, обозначающий его присутствие.
  Объект Б - х11х, В - 1ххх.
  Необходимо сделать сортировку.

Предпожим, что массив выглядит:
1 - 0001 - А
2 - 0111 - АБ
3 - 1001 - АВ
4 - 1110 - БВ
5 - 1111 - АБВ

После сортировки он должен выглядеть:
1 - 0001 - А
2 - 0111 - АБ
5 - 1111 - АБВ
2 - 1001 - АВ
4 - 1110 - БВ

Так?

[darkelf]

Предпожим, что массив выглядит:
1 - 0001 - А
2 - 0111 - АБ
3 - 1001 - АВ
4 - 1110 - БВ
5 - 1111 - АБВ

После сортировки он должен выглядеть:
1 - 0001 - А
2 - 0111 - АБ
5 - 1111 - АБВ
2 - 1001 - АВ
4 - 1110 - БВ

Так?

Я понял это немного не так, в том смысле, что под каждую "Букву" - один бит:
1 - 0000 - ""
2 - 0001 - "А"
3 - 0010 - "Б"
4 - 0011 - "АБ"
5 - 0100 - "В"
6 - 0101 - "АВ"
7 - 0110 - "БВ"
8 - 0111 - "АБВ"
и т.д. А у Вас получается, что под букву "Б" - два бита.
Соответственно сортировка:
1 - 0000 - ""
2 - 0001 - "А"
3 - 0010 - "Б"
5 - 0100 - "В"
4 - 0011 - "АБ"
6 - 0101 - "АВ"
7 - 0110 - "БВ"
8 - 0111 - "АБВ"
Возможно, я тоже понял не правильно, но я пытался уложить то самое:

0х0009 > 0х0001:  1+4  > 1

но

0х0009 < 0х0006:  1+4 < 2+3

[ezus]

Интересно получилось.
Оба правы и оба ошиблись.
Понятно, что это моя вина.

darkelf прав в трактовке символов, каждому символу 1 единичка.

А у Aether правильная сортировка, сначала по 1-му символу в слове(!не по позиции!), потом по 2-му, если он есть, потом по 3-му....

[Aether]

Тогда стоит обратить внимание:
  серия Аххх
0001
0011
0111
1111
  серия Бхх
0010
0110
1110
  серия Вх
0100
1100
  серия Г
1000
  всё остальное
0000
Принцип составления этих тетрад вполне понятный, а алгоритм сортировки:
1) Выделяем буфер размером 1 запись.
2) Устанавливаем указатель старта i_st=1 и указатель сканирования i=i_st.
3) Перебираем список записей i++ до N пытаясь найти слово 0001 (из предварительно сгенерированного списка, но уже не тетрад, а 16бит).
4.1) Если слово найдено, то меняем через буфер местами записи i_st и i,
далее i_st++;
4.2) Если достигнуто i=N, и оно не соответствует 0001, то:
   i=i_st+1; i++ до N, всё по аналогии, но со словом 0011.
5) Когда дело дойдёт до 1000 сортировку можно завершать - в остатке останутся "нулевые" записи.
Тут ещё есть вторая проблема: две записи могут иметь одну маску, но, например, разные даты создания или порядковые номера по заполнению, так что внутри категории, возможно, тоже придётся делать сортировку, чтобы было:
А - 12:17
А - 14:10
АБ - 13:43
АБВ - 15:17
БВ - 9:33
...

[darkelf]

ezus, у меня получилось что-то типа такого:

Код: (C)

int cmp(unsigned short* m1, unsigned short* m2)
{ int i;
  unsigned short mm1 = 0, mm2 = 0, mm = 3;

  if (*m1 == *m2)
    return 0;

  for (i = 0; i < 16; i++)
  { if ((*m1 & (1 << i)) != (*m2 & (1 << i)))
      break;
  }

  for (; i < 16; i++)
  { if ((mm & 1) && (*m1 & (1 << i)))
    { mm1 = *m1 & (1 << i);
      mm &= ~1;
    }
    if ((mm & 2) && (*m2 & (1 << i)))
    { mm2 = *m2 & (1 << i);
      mm &= ~2;
    }

    if (mm == 0)
      break;
  }

  return ((int)mm1 & 0xffff) - ((int)mm2 & 0xffff);
}

ну, или, к 1-вому апреля, можно и такой вариант (он точно работает):

Код: (C)

char* mask_to_string(char* str, unsigned short mask)
{ char* p = str;
  int i;

  for (i = 0; i < 16; i++)
  { if (mask & (1 << i))
      *p++ = i + 'A';
  }
  *p++ = 0;

  return str;
}

int cmp(unsigned short* m1, unsigned short* m2)
{ char s1[17];
  char s2[17];

  mask_to_string(s1, *m1);
  mask_to_string(s2, *m2);

  return strcmp(s1, s2);
}

для проверки:

Код: (C)

int main(int argc, char* argv[])
{ char s1[17];
  unsigned short masks[] = { 7, 0x4000, 5, 8, 2, 9, 0, 0x4001, 3, 1, 0xf};
  int i;

  qsort(masks, sizeof(masks) / sizeof(masks[0]), sizeof(masks[0]), cmp1);

  for (i = 0; i < sizeof(masks) / sizeof(masks[0]); i++)
    printf("%04x %s\n", masks[i], mask_to_string(s1, masks[i]));

  return 0;
}

[ezus]

To darkelf: Собственно процедура сортировки меня не интересует. т.к. на входе я имею уже сортированные последовательности, а алгоритм должен обеспечить сортировку выходной последовательности, что он добивается пробегом всех входных последовательностей   одновременно( в рамках одного цикла ). Для этого надо сравнивать элементы разнах последовательностей на больше\меньше.

To Aether : Да, что-то в этом роде у меня сначала и было, но я хотел избежать циклов, которые, находясь на самых вложенных уровнях, жрут чувствительное время, когда выполняются 10-ки млн. раз.

К счастью общий алгоритм требует строгой упорядоченности последовательностей - и только. Т.е. ему все равно вверх или вниз.
Поэтому я заменил сортировку на убывающую, и теперь просто сравниваю маски.
Но это не очень красиво и в дальнейшем может привисти к неприятностям, поэтому я и пытаюсь найти что-нибудь приличное для возрастающей сортировки.

Но похоже без циклов не обойтись.

Спасибо.
 

[darkelf]

To darkelf: Собственно процедура сортировки меня не интересует. т.к. на входе я имею уже сортированные последовательности, а алгоритм должен обеспечить сортировку выходной последовательности, что он добивается пробегом всех входных последовательностей   одновременно( в рамках одного цикла ). Для этого надо сравнивать элементы разнах последовательностей на больше\меньше.

Эту функцию (cmp()) можно использовать и просто для сравнения - она правильно сравнит две маски с учётом Ваших условий. Но к сожалению да, с циклами.

[darkelf]

ezus, кстати, если немного развить алгоритм, то можно и реализовать то, что Вы хотели с самого начала

По возможности без циклов

Я хотел найти, что-нибудь типа подсчета единиц в байте одной командой - путем адресации к таблице из подготовленных заранее 256 количеств.

просто сначала построить такую таблицу, а потом её везде использовать.

Код: (C)

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

char* mask_to_string(char* str, unsigned short mask)
{ char* p = str;
  int i;

  for (i = 0; i < 16; i++)
  { if (mask & (1 << i))
      *p++ = i + 'A';
  }
  *p++ = 0;

  return str;
}

struct mask_entry
{ unsigned short mask; /*маска*/
  unsigned short weight; /*вес маски*/
};

/*функция сравнения для лексикографической сортировки масок*/
int cmp0(void const* v1, void const* v2)
{ int i;
  unsigned short msk1, msk2, mm1 = 0, mm2 = 0, mm = 3;
  struct mask_entry* m1 = ((struct mask_entry*)v1), *m2 = ((struct mask_entry*)v2);

  msk1 = m1->mask;
  msk2 = m2->mask;

  if (msk1 == msk2)
    return 0;

  for (i = 0; i < 16; i++)
  { if ((msk1 & (1 << i)) != (msk2 & (1 << i)))
      break;
  }

  for (; i < 16; i++)
  { if ((mm & 1) && (msk1 & (1 << i)))
    { mm1 = msk1 & (1 << i);
      mm &= ~1;
    }
    if ((mm & 2) && (msk2 & (1 << i)))
    { mm2 = msk2 & (1 << i);
      mm &= ~2;
    }

    if (mm == 0)
      break;
  }

  return ((int)mm1 & 0xffff) - ((int)mm2 & 0xffff);
}

/*функция сравнения для сортировки масок в порядке их числовых значений*/
int cmp1(void const* v1, void const* v2)
{ struct mask_entry* m1 = ((struct mask_entry*)v1), *m2 = ((struct mask_entry*)v2);
  return ((int)m1->mask - (int)m2->mask);
}

#define N_MASKS 65536

/*функция подготовки таблицы весов масок*/
unsigned short* prepare_mask_table(void)
{ struct mask_entry* me;
  unsigned int i;
  unsigned short* masks;

  me = malloc(N_MASKS * sizeof(*me));
  if (me == NULL)
    return NULL;

  for (i = 0; i < N_MASKS; i++)
    me[i].mask = i;

  /*сортируем в лексикографическом порядке*/
  qsort(me, N_MASKS, sizeof(*me), cmp0);

  /*назначаем веса масок - вес маски - её индекс в таблице*/
  for (i = 0; i < N_MASKS; i++)
    me[i].weight = i;

  /*возвращаем исходный порядок*/
  qsort(me, N_MASKS, sizeof(*me), cmp1);

  masks = malloc(N_MASKS * sizeof(*masks));
  if (masks == NULL)
  { free(me);
    return NULL;
  }

  /*возвращаем таблицу*/
  for (i = 0; i < N_MASKS; i++)
    masks[i] = me[i].weight;
  free(me);

  return masks;
}

/*сравнение двух масок, без циклов "одной" командой*/
#define MASK_CMP(wmasks, m1, m2) ((int)(wmasks[(m1)]) - (int)(wmasks[(m2)]))

int main(int argc, char* argv[])
{ char s[17], s1[17];
  unsigned short* wmasks;
  int rez;
  unsigned short mask = 7;
  unsigned short mask1 = 0x8000;
  char* p;

  wmasks = prepare_mask_table();

  rez = MASK_CMP(wmasks, mask, mask1);
  if (rez == 0)
    p = "=";
  else
  if (rez < 0)
    p = "<";
  else
      p = ">";
  printf("%04x (%s) %s %04x (%s)\n", mask, mask_to_string(s, mask), p, mask1,  mask_to_string(s1, mask1));

  free(wmasks);

  return 0;
}

Соответственно сравнение масок будет простым макросом, без циклов и т.д.
Можно такую таблицу вообще заготовить предварительно, в виде *.c-шного файла.

[ezus]

То darkelf
Спасибо за алгоритм.
Я правильно понял, что предварительно строится таблица, в которой каждой маске(2^16) соответствует строка символов, иммитирующая инвертированую(начало\конец) маску? А затем в процессе работы для сравнения 2 масок мы одной командой получаем доступ к началу соответствующей строки и затем лексико-графически сравниваем строки для этих масок?

[darkelf]

То darkelf
Я правильно понял, что предварительно строится таблица, в которой каждой маске(2^16) соответствует строка символов, иммитирующая инвертированую(начало\конец) маску? А затем в процессе работы для сравнения 2 масок мы одной командой получаем доступ к началу соответствующей строки и затем лексико-графически сравниваем строки для этих масок?

Прошу прощения, как-то потерял из виду эту тему..
По поводу вопроса - типа того, мы создаём массив масок и сортируем элементы массива масок по весам, а затем возвращаем массив весов этих масок, отсортированный по значениям масок. Т.е. индексом в массиве будет значение маски, а значением по этому индексу - вес маски.