Сделал на раз - цикл до x + вложенный цикл. Количество итераций = sum[x], которое при x=3000 в моем случае совершенно неприемлимо. Подскажите алгоритм, определяющий моду за один проход.  

Это сообщение отредактировал(а) Golden Hands - 16.5.2006, 14:52

мода, если мне память не изменяет, это максимум?
максимум ищется за один проход (в переменной надо сохранять параметры текущего максмума) 

мода это элемент встечающийся максимальное число раз 

Мода возвращает наиболее часто встречающееся значение в массиве данных. Причем:
1) Если массив не содержит одинаковых значений, мода не может быть подсчитана.
2) Если несколько значений встречаются одинаковое число раз, мода равна тому значению, которое встречается первым. 

Аааа... я почему-то подумал, что у нас уже массив вероятностей...

Добавлено @ 00:38 
можно попробовать так:
1. сортируем массив - log(n)*n
2. идём по нему, считая длину непрерывной последовательности элементов и сравнивая с наиболее длинной из ранее встреченных 

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

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

в лучшем случае на это понадобится log(n) - это если хранить в упорядоченном массиве... только тогда добавление будет дольше... 

Нет, вычисляем хэш от очередного числа и находим его индекс. Никакого log(n). 

Зачем в массиве?  Есть бинарное дерево поиска. Немного модифицируем - добавим в узел поле count, которое будет указывать сколько раз встречается данный элемент.

Мы можем использовать добавлять элемент из массива бинарное дерево следующим образом:
1) если узла с таким элементом в дереве ещё не было, то он добавляется как в обычное бинарное дерево поиска, и node.count <- 1
2) если узел с таким элементом есть, то мы увеливаем у узла count.


далее проходим по всему дереву и ищем максимум.

 

Вот, собстно, что у меня сейчас. Кидаю паскалевский код, т.к. блок-схемы подзабыл   


element - массив исходных значений, count - массив для подсчета числа вхождений элемента.




Есть вариант вставить цикл (между 5 и 6 строками в коде), который будет проходить по всему массиву element и разрешать выполнение (строка 6) только в том случае, если текущий элемент не входит в этот массив. Но тогда:
1) Если вхождение установится быстро, то все ОК.
2) Если вхождение установится в самом конце прохода, то получится двойная трата времени, чем было бы без проверки вхождений.  

Это сообщение отредактировал(а) Golden Hands - 16.5.2006, 11:56

если min/max числа в разумных пределах, можно прямо таблицу составить, где индекс - само число. при каждом последующем числе х увеличиваем на еденицу значение массив[х] и сравниваем с МОД'ом из предидущей итерации.
(В принципе тот же хэш, предложенный nostromo, хо с функцией hash(x)=x) 

Ну ты заврал про кол-во итераций. Их не квадрат...

Как уже предлагал Mayk, а может я не так понял, создадим новый тип, который будет хранить два значения- сама цифра и кол-во её вхождений в множество. Причем у каждого последующего элемента с одинаковой "цифрой" кол-во её вхождений будет на 1 больше. К примеру: цифра 6 встречалась два раза на момент начала действия,тогда было
6,2;
Появилась еще одна шестерка. И стало
6,2;
6,3;
И далее:
6,2;
6,3;
6,4;
И затем просто ищи максимум среди кол-ва вхождений. 

Поиск в бинарном дереве как раз и имеет сложность log(n) 

SoWa, двумерный масив предлагаешь? Я обдумывал это, сейчас еещ прикину. 

НЕЕЕ. не двумерный. А вот так:
 

SoWa, начну с реализации твоей идеи. 

я бы уточнил: поиск в сбалансированном бинарном дереве пропорционален log(n)

в худшем случае он пропорционален n, так что придётся тратить время на балансировку
...
впрочем, и быстрая сортировка в худшем случае пропорциональна n^2 

если есть достаточно памяти (ещё столько ж, сколько занимает массив), то лучше сортировка слиянием - она гарантированно занимает n*log n... 

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

 

Временные затраты очень малы. Что и следовало...    

Всех благодарю за участие! 

Это сообщение отредактировал(а) Golden Hands - 16.5.2006, 14:51

С вариантом nostromo, будет значительно быстрее. 

Добавление в отсортированный массив занимает в худшем случае линейное время.
(дан массив (2,3,4,5). Для того чтобы добавить в него 1 понадобится скопировать ВЕСЬ массив).
В случае сбалансированного(как справедливо отметили выше) бинарного дерева добавление возможно за log(n) 
  

Это сообщение отредактировал(а) Mayk - 17.5.2006, 06:21

1) Во-первых, ваше "что алгоритм работает за один проход только в случае, когда"   .... неверно


2) Во-вторых в общем случае ваш алгоритм работает за х*лог х времени.


с ув 

конечно же. нет. 

Сейчас, сейчас...

Критерием истины, как известно, является практика, поэтому приступим.

Пусть входными элементами будут целые числа, а в качестве хэш функции
возьмем остаток от деления на фиксированное число (bufSize).
Список частот (currFreq) будем хранить в массиве размера bufSize.
На случай коллизий, в каждом элементе currFreq будем хранить список пар
(<число> @ <частота>).

Программу напишем на Smalltlak (VisualWorks). В этой простой задаче обойдемся стандартной библиотекой и новых классов создавать не будем. 

Собственно программа:


Проверяем работу:


Проверяем зависимость вермени работы от размера входного массива,
в котором записаны случайные числа.
Сначала пусть случайные числа будут в диапазоне от 1 до 100 (много коллизий)

--- очевидно, линейный рост времени исполнения, накокого n*log(n).

Теперь случай, когда случайные числа в диапазоне от 1 до 10^7 (мало коллизий):

--- в этом случае требуется заметно больше памяти (больше элементов попадает в currFreq, плюс сами числа требуют больше памяти --- Smalltalk автоматически перобразует целые числа, в первом случае они влазили в Smallint (два байта)), 
поэтому линейная асимптотика для больших значений немного испорчена сборщиком мусора. 
В случае асимптотики n*log(n) время на каждом шаге должно было бы
вырастать в 4 раза.

Добавлено @ 14:55 
Небольшая поправка, в последнем тесте
counts := #(1000 2000 4000 8000 16000 32000 64000 128000 256000 512000).
(Не оттуда скопировал.) 

nostromo, отлично, только надо учесть негативные числа в хэш-функции (то есть брать |х| ) 

Виноват, это совсем не так. Зависимость сложнее:
если n пробегает ряд
(2 4 8 16 32 64 128 256  512),
то n*log(n) пробегает ряд: 
(2 8 24 64 160 384 896 2048 4608).

Отсюда следует, что в случае, если алгоритм с линейной сложностью имеет большой константный множитель по сравнению с алгоритмом с асимптотикой n*log n, то последний может оказаться предпочтительнее для довольно широкого диапазона значений (логарифм очень медленно растет). Однако подозреваю, что в рассматриваемой задаче линейный алгоритм лучше.

Добавлено @ 15:48 
sergej.z, спасибо.  

Я конечно еще раз извенюсь.

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

А ваше численные примеры, лишь смущают не ведующих. А на самом деле профанация чистой воды.


с уважением 

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

если исследовать поведение хеша при n->oo, то он принципиально ничем не отличается от того же бинарного дерева (только у узлов там не два, а куча потомков, да и уже на втором уровне деревянная структура может не сохраняться), а значит поиск по хешу ("хорошему" хешу, что эквивалентно сбалансированности дерева) будет занимать log n (да и то, это если на втором уровне не делать чего-то типа списка/массива)

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

Это сообщение отредактировал(а) maxim1000 - 17.5.2006, 23:43

Уважаемый esperant0, по-видимому, наши разногласия связаны с различным пониманием постановки задачи, что верно заметил maxim1000.

Еще раз попробую внести ясность.

1. На вход алгоритма поступет массив M из N элементов.
2. Допущения:
    1.1. Оперативной памяти всегда достаточно, сборкой мусора, особенностями операционной системы и другими внешними факторами пренебрегаем.
    1.2. Всегда есть возможность за фиксированное время в зависимости от N настроить парметры хэш-функции так, чтобы она выдавала значения от 1 до некоторого N1 (также зависящего от N) с пренебрежимо малым числом коллизий.
    1.3. Выделение памяти под вспомогательный N1-элементный список частот занимает фиксированное время, не зависящее от N1 (или зависящее пренебрежимо слабо).
    1.4. Доступ к элементу массива (или списка) по его индексу всегда занимает фиксированное время.
3. Алгоритм.
    3.1. Инициализация. Выбирается хэш функция, со свойствами, описанными в 1.2 и создается список частот M1 размера N1. (В списке частот хранится текущее количество встреч элементов.) Инициализируются переменные для значения элемента, который встречается максимальное число раз и частота его встречи (нулем).
    3.2. Последовательно в цикле перебираются элементы входного массива M 
и для каждого из них выполняются следующие действия.
        3.2.1. С помощью хэш функции вычисляется индекс элемента в списке частот.
        3.2.1. По индексу находится элемент списка частот и инкрементируется значение текущего числа встреч элемента. (Выполнение этого пункта занимает фиксированное время --- это следует из предположения о пренебрежимо малом числе коллизий хэш функции.)
        3.2.3. Проверяется, не превосходит ли число встреч текущего элемента рекордного значения и, если превосходит, рекордное значение обновляется.
4. Очевидно, что при указанных допущениях, от размера входного массива зависит только число итераций цикла --- оно совпадает с N, значит, сложность алгоритма --- линейная.
 

1.2 не реабельно. то есть не выполнимо в общем случае 

Да ну? А что такое общий случай?

С точки зрения практики, этот пункт один из самых легко достижимых.
Могу предложить универсальный способ для любых объектов.
Хэш функция выглядит следующим образом:
входной объект, сериализуется в строку, вычисляеется от нее MD5-хэш,
он, в свою очередь, берется по модулю параметра K. Все.
Настройка хэш функции, осуществляемая в секции инициализации алгоритма, заключается в установке значения K, например, равным числу элементов входного массива. 
Здесь скорее проблема придумать хороший контрпример.

Предложенный алгоритм поиска моды имеет линейную сложность (от размера входного массива) и в теории и на практике (пока хватает оперативной памяти), а Вы, кажется, просто не хотите это признать.

Добавлено @ 09:02 
Если подходить совсем строго, с теоретической точки зрения для любого произвольного входного массива, о котором вообще ничего не известно, кроме числа элементов, действительно нельзя гарантированно предложить хэш функцию с малым число коллизий. Однако на практике, это почти всегда возможно, плюс, с самого начала я говорил, что алгоритм имеет линейную сложность при условии существования "хорошей" хэш-функции.
 

Я свами и не спорю.

Обычно алгоритмы оценивают, с точки зрения худшего случая. В худшем случае ваш алгоритм не линейный.

Говорить же про средний случай, уместно лишь при задании вероятностного распределения на входных данных, которое автор вороса, вроде как не задал.


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

Значит, быстрая сортировка имеет асимптотику n^2?

На множестве входных массивов, для которых есть возможность выбора "хорошей" хэш функции алгоритм получается линейный. Мне показалось, Вы с этим спорили.

P.S. Кажется, пора закругляться.
 

Ассимптотика и худший случай разные вещи.

худший случай вероятностного алгоритма быстрой сортировки п^2 но вероятность этого случая не зависит от распределения входных данных и экспоненциально мала от п.

В вашем же случае худший случай есть и для определенного вида данных. Ваш алгоритм не линейный.


резюмы: вы решили не задачу автора, а модифицировали задачу, дополнив ее некоторым ограничением. Кроме, того вы так и не привели докозательство правильности работы.


Вот решение аналогичное вашему. Предположим что для исходного массива выполнены условия применения ведерной-сортировки (backet sorting) отсортируем массив за линейное время и найдем в нем моду.


Это решение не хуже и не лучше вашего. Правда оно лучше тем, что док-во его правильности более прозрачно.

с ув. 

Этого не понял, какой-такой плохой вид данных?
Укажите пожалуйста, какой пункт алгоритма, кроме перебора значений входного массива требует времени, зависящего от N. По поводу пункта 1.2 я уже ответил.

В чем я модифицировал задачу автора. Я лишь указал, что мой алгоритм будет иметь линейную сложность при условии существования подходящей хэш-функции (устал это повторять). 
Доказать правильность работы алгоритма означает доказать, что он правильно находит моду. Идея алгоритма тривиальна: последовательно просматривая входной массив подсчитываем и сохраняем во вспомогательной структуре число встреч каждого элемента, следя за текущим рекордным значением. Вам действительно неочевидно, что в результате будет найдены мода? Что именно неочевидно?


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

А почему вы для доказательства своей правоты увеличиваете n до бесконечности, но при этом не увеличиваете оперативку до бесконечности? 

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

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

 удалено 

извиняюсь


"А почему вы для доказательства своей правоты увеличиваете n до бесконечности, но при этом не увеличиваете оперативку до бесконечности? 

На практике хэш - вариант бесспорно даст лучшие результаты. Потому что интересует только скорость. память докупается по необходимости. "



Для доказательства правоты не используют симуляция, в данном вопросе. Необходимо дать четкое формальное доказательство.

Употребление Вами слова беспорно, тут не корректно, во-первых оно не верно. Во-вторых спорно. 

Кроме того существует класс задач, для которых память критичней времени.

с ув.

 

Это сообщение отредактировал(а) esperant0 - 27.5.2006, 14:00

В таком тоне здесь никакой дисскуссии не будет.
Пожалуйста, используйте деревья.


Это по моему очевидно. А вот у дерева алгоритм линейным не получиться ни в каком случае.