Мелкие задачки для крупных мозгов 14

Дан массив чисел (dwords)(например длин из предыдущих задач)

и его длина .

выделить правильно память для таблицы множества на котором построен массив (мощность * 4*2 + 4)

создать таблицу статистики следующего формата.

dword - количество записей в таблице

записи (

dword значение из массива чисел

dword сколько раз встречается в массиве)



Это уже задачки "среднего уровня" - алгоритмически и математически правильное решение превалирует над машинной оптимизацией. Различатся различные решения могут до квадратного корня от менее эффективного и более.



Примечание - массив чисел не может быть пустым, более того он достаточно большой до 2^27 элементов.

 

The Svin

> "например длин из предыдущих задач"



Боюсь надоесть своими примечаниями, но задачку можно упростить ограничив максимальную анализируемую длину битовой строки. Если речь идет об анализе сигналов из 11й задачки, то ИМХО длительность сигнала ожидания никакой полезной инфрмации не несет. Это м.б. совершенно случайная величина, которая будет понапрасну пожирать место в множестве длин. Поэтому можно ограничить макимальную длину строки в множестве (гистограмме распределения) некоторой разумной величиной, а все что больше или игнорировать или суммировать кол-во в отдельной (последней) ячейке. Если для суперанализатора нужно распределение интервалов ожидания, то ИМХО точные значения длин здесь не нужны и можно копить данные в отдельном множестве с огруглением длин до некоторой величины, кратной степени 2.



При таком подходе множество "коротких" длин может выродиться в простой массив, где индекс = длине. И длину хранить не нужно, и размер массива заранее определен, а о скорости и говорить нечего. Тогда "таблицу статистики следующего формата" можно строить только для больших длин.

Кстати нечто подобное используется в менеджерах динамической памяти - раздельное хранение ссылок на малые блоки (прямой доступ) и на большие блоки (поиск\перебор).



Что скажешь ? Или это не в ту степь ?

 

Не в ту

Просто относимся к задаче как одной из самых распространённых из в области СУБД - выбрать по одному все встречающиеся значения. И дерзаем.

Пусть допустим мы и приняли условия фильтрации, далее то всё одно нам нужен алгоритм выборки множества из оставшихся.

 

Сортируем и выбираем.. наверное не самое плохое решение.

 

1. Фраза сравнительная, непонятно с чем сравниваем,

"не самое плохое" из каких?

2.

Сортировать и выбирать можно по разному, нужно показать код.

3. Изменять (сортировать) оригинальный массив нельзя, на его дубликат может не хватить память, нужна ведь ещё память и на выборку. А изначальный массив может быть довольно большим.

 

Запихать массив в хеш-таблицу. Если появляется коллизия - значит dword просто выбрасывать, а счетчик увеличивать.

 

volodya

Ничего не понял Код нельзя ли продемонстрировать?

 

Ничего не понял



Странно, почему я не удивлен?



Код нельзя ли продемонстрировать



Нет, нельзя. Только псевдокод. На код времени не имею.



Предположение (т.к. вы не указали): массив на вход неотсортирован.

Код (Text):

1.  
2. DWORD arr[]; //массив на вход
3. hash_table h_table; //хеш-таблица
4.  
5. for(от начала массива до конца поэлементно)
6. // пусть arr[i] такой элемент
7. {
8.     DWORD index = hash_func(arr[i]);
9.     if(hash_table[index] существует)
10.     {
11.       hash_table[index].counter++;
12.     }
13.     else
14.     {
15.       создать такой элемент и выставить counter в 1;
16.     }
17. }
18.  

Некоторые пояснения. Итак, т.к. вами явно не указано, я предполагаю, что значение DWORD в массиве может быть любым, т.е., положим i принадлежит DWORD массив, тогда диапазон значений i: 0 <= i <= 0xFFFFFFFF. Следовательно, мы не можем применять простой поиск по индексу напрямую, т.к. в худшем случае под такой индекс надо будет отводить 0xFFFFFFFF памяти и большая часть этой памяти будет израсходована впустую. Какой выход? Выход очевиден. Берем хеш-функцию для чисел и сводим все дело к некоторому индексу. Далее по этому индексу выполняем простой поиск в хеш-таблице - это константное значение, быстрее этого не может быть ничего. При возникновении коллизии (что означает, что ячейка уже чем-то занята, иными словами, мы уже встречали этот DWORD ранее), мы просто инкрементируем связанный с ней счетчик.



На перле пишется за несколько минут Кстати, Sten ранее в форуме уже предлагал решение такой задачи, откуда я его по памяти и взял

 

volodya

Я тоже ничего не понял. Мне наивному чукче представления о магии хэш-таблиц напоминают, однако, басни барона Мюнхгаузена, а также колдовство алхимиков и изобретателей вечного двигателя



Тезис 1:

> простой поиск в хеш-таблице - это константное значение, быстрее этого не может быть ничего

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



Тезис 2:

> положим i принадлежит DWORD массив, тогда диапазон значений i: 0 <= i <= 0xFFFFFFFF

Что из этого следует ? Если отбросить алхимию, то из этого следует, что хэш без коллизий должен принадлежать этому же диапазону - однозначное отображение множеств, однако. А зачем тогда нужно это отображение - чем один dword лучше другого ? Ничем. Вывод: хэш без коллизий в данном случае - это шило на мыло, т.е. алхимия. Поэтому, если мы хотим уменьшить диапазон значений хэша, то коллизии теоретически неизбежны и алгоритм должен предусматривать их обрабатку.



Что из этого следует:

Имхо, бинарные деревья (в которых я не силен, особенно в вопросах балансировки), либо хэш-таблица с коллизиями.

Если ограничений по статистике нет и все числа равновероятны, то в качестве хэша можно брать N младших бит числа, т.к. это теоретически не лучше и не хуже чем сложная функция, а практически намного быстрее. Для обработки коллизий элемент таблицы должен дополнительно содержать ссылочку на структуру (массив, список, дерево), в которой хранятся коллизии - элементы с тем же значением хэша.

Выбор в качестве хэша младших бит числа также даст выигрыш по средней скорости поиска для задачки обработки длин сигнала, когда малые длины намного более вероятны, чем большие (как в задачке 11). При этом и память можно несколько сэкономить (наверное, хотя не очевидно) - элемент таблицы будет содержать только счетчик для чисел менее N бит и ссылку на cписок коллизий (т.е. большие числа с совпадающими младшими битами). Неочевидность экономии памяти в том, что реально различающихся малых значений будет не много, и прочие элементы будут содержать только ссылки на коллизии, а поле счетчика будет пустым. Можно помозговать - нельзя ли упаковать в один dword старшие биты числа и индекс-ссылку на структуру коллизий. Структура хранения коллизий тоже от статистики зависит - если больших чисел сравнительно немного, то можно и голову особо не ломать и хранить их в едином сортированном массиве, тогда и ссылки на коллизии не нужны и доп.экономия памяти (на это я и намекал в предыдущем посте). Иначе - списки или деревья и => дополнительная память на ссылки на следующий элемент (хотя если реально их будет не много, то тоже ничего страшного).



Вывод: хэша таблица - это хорошо, но не так просто и радужно Или я все-таки чукча, и чего-то не понимаю, однако

 

Если сравниваемые значения - числа, то использование одного числа вместо другого ничего не дает в плане скорости сравнения



В плане скорости сравнения - да. Но в плане сужения диапазона с 0 <= i <= 0xFFFFFFFF до 0 <= index <= hash_func() - дает еще как!



Если отбросить алхимию, то из этого следует, что хэш без коллизий должен принадлежать этому же диапазону - однозначное отображение множеств, однако



А я РАЗВЕ ГДЕ-ТО СКАЗАЛ, что ХЕШ БЕЗ КОЛЛИЗИЙ, а??? Как ты читал? Как ты на псевдокод смотрел???



и алгоритм должен предусматривать их обрабатку.





ну и что я могу тут сказать? могу только повторить - на псевдокод смотри!!!



Что из этого следует:

Имхо, бинарные деревья (в которых я не силен, особенно в вопросах балансировки), либо хэш-таблица с коллизиями.



Что я и предложил. А как ты читал - пардон, ничем помочь не могу

 

Итак, таки написал код, чтобы убедить страждущих.



На перле:

Код (Text):

1.  
2. use strict;
3.  
4. my @arr = (1,2,3,4,4,4,5,6,7,8,8);
5. my %hash;
6.  
7. foreach (@arr)
8. {
9.     if(exists $hash{$_})
10.         {$hash{$_} += 1;}
11.     else
12.         {$hash{$_} = 1;}
13. }
14.  
15. foreach my $key (keys %hash)
16.     {print "key is: ".$key." value is: ".$hash{$key}."\n";}
17.  

Чтобы написать сие на С/С++ - требуется создать свою реализацию хеш-таблицы. Например, такую, как предлагается тут:



http://www.rsdn.ru/article/alg/bintree/hash.xml



Чтобы написать сие на асме - вот тут уже совсем весело Воссоздавать с нуля у мя времени нет. Библиотек с реализациями хеш-таблиц на асме не знаю. Надо гуглить.

 

volodya

Я и в самом деле из тундры, т.к. в перле не бум-бум.

Но все таки, попытаюсь возразить- оправдаться, т.к. одно дело что ты написал, другое дело что на самом деле имел в виду.



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

1) "index = hash_func(arr)" - в случае коллизии двум разным значениям arr, например, 3 и 7 будет соответствовать одно и тоже значение index, например 5.

2) "если hash_table[index] существует". Думаю при любых допущениях и предположениях эту запись можно расценить только как отображение единственного числового значения index во что-то другое (в данной записи в логический тип да\нет). Допустим на предыдущем шаге ранее было arr = 3 и мы выполнили одно из действий if..else с index = 5. Теперь нам попалось значение arr = 7, которое тоже отображается в index = 5. Вопрос: что в данном случае мы получим в результате операций "если hash_table[index] существует" и "hash_table[index].counter++;". Я эти псевдозаписи могу расценить не иначе как, одинаковую реакцию на входное значение index = 5, а следовательно и неразличимость двух разных чисел 3 и 7 и => неверный результат и => приведенный псевдокод может работать тольки при отсутствии коллизий.

Или я плохо смотрел и неправильно интерпретировал, или ты поспешил - "один пишем, два в уме" ?



А со статейкой "Хэширование" я знаком. Там-то как раз все правильно записано: функция поиска принимает в качестве параметра не хэш-index, а само искомое значение, т.к. если элемент занят, то нужно еще уточнить каким именно значением.



Ну да ладно, это я так - придираюсь к неточностям (моська лает на слона

 

Я не слон. Я клуша. У которой в башке дикий хлам стоит. Недавно бедного Стена в нокдаун отправил. Отпуск нужен...



Так вот, касательно твоего замечания. Я просто неправильно выразился - ты прав. Хеш-функция нужна для одной цели - сузить диапазон, чтобы можно было использовать поиск по индексу. Разумеется, по возможности, функция должна давать минимально возможное количество коллизий (т.е. РАЗНЫЕ числа -> одно число). Поэтому нужна хорошая хеш-функция для чисел. Пример таких можно взять из Седжвика.

 

Примером хеш-функции может быть банальный %2 (остаток от деления на 2). Эта функция просто разделит все числа из массива на чётные и нечётные. Но если все (или подавляющее большинство) числа окажутся, например, чётными, то такая хеш-функция нисколько не ускорит алгоритм. T. Niemann рекомендует использовать в качестве модуля простое число, но не очень близкое к степени двойки. В его книге (лежит на сайте), в главе про hashtables есть даже про (sqrt(5) - 1)/2 в качестве хеша. Коллизии, между прочим, явление даже полезное, для сокращения индекса (dictionary) таблицы хеш. Главное - чтобы коллизии происходили равномерно по всем столбикам хеша.

 

Ничего я не понял ни про "сужение диапазона" ни про хеш.

Зачем хеш? Хранить в хеше выборку? Это не отвечает условиям задачи. В задаче выборка должна быть в бинарных значениях, тех же что и массив из которого осуществляется выборка. Быстрее будет? С чего это будет быстрее то данные поддерживаются процессором, будет линейное замедление на размер цикла кеширования и больше ничего.

Про диапозон вообще ничего не понял.



Может быть задача всё ещё не понятна?

Пример

на входе массив

100,101,100,102,102,101,99,100

на выходе

4 ; сколько записей

100,3, ; число 100 встречается 3и раза

101,2,

102,2

99,1

 

Да вот насчёт "хешей на ассемблере" - у Кнута полно.

Там всё на ассемблере

 

Пример

на входе массив

100,101,100,102,102,101,99,100

на выходе

4 ; сколько записей

100,3, ; число 100 встречается 3и раза

101,2,

102,2

99,1



Свин, сугубо по вашему примеру:

Код (Text):

1.  
2. use strict;
3.  
4. my @arr = (100,101,100,102,102,101,99,100);
5. my %hash;
6.  
7. foreach (@arr)
8. {
9.     if(exists $hash{$_})
10.         {$hash{$_} += 1;}
11.     else
12.         {$hash{$_} = 1;}
13. }
14.  
15. foreach my $key (keys %hash)
16.     {print "key is: ".$key." value is: ".$hash{$key}."\n";}
17.  

Результат:

Код (Text):

1.  
2. key is: 99 value is: 1
3. key is: 102 value is: 2
4. key is: 101 value is: 2
5. key is: 100 value is: 3
6.  

А если не отвечает условиям задачи - пардон, выразитесь яснее. Так, чтобы и я понял.



P.S. Кнутовский MIX выбросить. Зачем учить совершенно бесполезный язык?

 

The Svin

> "Ничего я не понял ни про "сужение диапазона" ни про хеш. Зачем хеш?"



Задача: сформировать из массива чисел таблицу соответствия value -> count, где value - значение числа из массива, count - сколько раз данное значение встречается в массиве. Идеальный критерий - максимум скорости & минимум памяти - на практике не достижим, за исключением тривиальных случаев, когда диапазон чисел заранее известен и числа пробегают все значения из этого диапазона. Поэтому задачка сводится к выбору некоторого компромиссного решения между скоростью и затратами памяти.



Максимум скорости обеспечивает таблица с прямым доступом, когда valuе = index таблицы. Пусть в твоем примере нам известно, что числа лежат в диапазоне 0..255 и количество значений каждого числа тоже не превышает 255. Тогда берем table = массиву из 256 байт, инициализируем нулями и затем для каждого value из массива просто инкрементируем table[value] - быстрее некуда. Но для приведенного примера массива (100, 101, 100, 102, 102, 101, 99, 100) у нас оказывается заполненными только 4 ячейки из 256 - слишком расточительно.

Вот тут на помощь и приходит хэш, который за счет небольшой потери в скорости (на вычисление хэша) позволяет уменьшить число строк таблицы если заранее известно, что число различающихся значений в массиве значительно меньше максимального значения (255). Теперь входом в таблицу является не само значение value, а hash(value). В рассматриваемом примере всего 4 различных значения идущих по порядку, поэтому идеальным хэшем без коллизий может быть например взятие 2 младших битов числа, т.е. hash = value and 3.

Тогда мы получаем хэш таблицу из 4 строк по два байта (valuе,count) - итого 8 байт вместо 256.

Код (Text):

1. hash -> (value,count)
2.  0   ->   (100,3)
3.  1   ->   (101,2)
4.  2   ->   (102,2)
5.  3   ->   ( 99,1)

Термин "сужение диапазона" в данном случае означает, что мы уменьшили число входов таблицы с 256 (диапазон значений value, до 4 (диапазон значений хэша).



Но в реальной задачке с неопределенными входными данными достичь такого идеала ес-но невозможно. Придется учитывать коллизии. Добавим в рассматриваемый массив число 103, тогда его hash = 103 and 3 = 3 совпадает с хэшем числа 99. Для учета коллизий возможны различные варианты (открытая адресация, метод цепочек и др. вариации). По сути хэш таблица дает нам разбиение всего множества значений на N подмножеств, где N - диапазон значений хэша (в данном случае = 4). Поэтому в методе цепочек в отличие от последовательного поиска значения по всему множеству мы по значению хэша получаем прямой доступ к подмножеству меньшего размера. Например, если бы мы хранили табличку в виде обычного массива или списка, то при добавлении числа 107 нам пришлось бы искать это значение в списке из всех значений, а при использовании хэш-таблицы мы сразу идем по индексу 3 и ищем нужное значение только среди этого подмножества hash = 3:

Код (Text):

1.  0   ->   (100,3) -> (104,1)
2.  1   ->   (101,2) -> (105,1)
3.  2   ->   (102,2) -> (106,2)
4.  3   ->   ( 99,1) -> (103,1) -> (107,2) ...

Ес-но при наличии коллизий общая структура хранения и поиска данных усложняется, поэтому и важна статистика входных данных чтобы правильно выбрать хэш (в первую очередь диапазон) и способ обработки коллизий (способ хранения и поиска).

 

Ага осталось только такую "быструю хэш функцию" получить да ещё чтоб она была биективна

 

Там язык a_s_s_e_m_b_l_e_r, если ты им уже владеешь, то учить язык программирования не надо. Другой лишь там машинный язык, для низкоуровневиков освоить ещё один новый машинный язык - не проблема. Тем более что он на порядки примитивней x86, и содержит на более чем 90% то что уже содержится в x86.



Кто придумал эту хренотень - замену определённых слов?

Позвольте выразить моё IMHO - Вы полный дундук, и если без ведома пользователей здесь не перестанут заменять их тексты - я с этой борды уйду. Я привык чтобы в текстах мной написанных было имено то, что я писал.