|
|
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Всем привет. Кто-нибудь знает самый эффективный алгоритм поиска одинаковых элементов списка ( массива) ? То что есть пока, это вот: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. Количество итераций для этого алгоритма (n^2 - n)/2 Есть предложения??:) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2007, 18:56 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Может посмотреть в направлении квиксорта? Типа отсортировать, потом за один пробег посмотреть повторы... Это я так, не думая))) может и не прав) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2007, 19:05 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Или более общий случай - построение B+ индекса по списку. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2007, 19:18 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
maytonИли более общий случай - построение B+ индекса по списку. это как? Есть ссылка на этот алгоритм? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.12.2007, 19:21 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
есть еще предлолжения? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2007, 00:58 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Ну, можно еще на хэшах сделать, примерно вот так: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2007, 10:07 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
po4talyon wrote: > есть еще предлолжения? Если число возможных элементов ограничено (например, каждый элемент - целое число до 32х бит (хотя лучше 16 , можно сделать битовое множество. (правда, для 32хбитного числа на это уйдет ~512мб рам, но, например, для char символов такой способ - самое оно.). Т.е. 1) обнуляем битовое множество 2) создаем пустой список - результат 3) пробегаем исходный список, для каждого элемента, если соответствующий бит не установлен, добавляем элемент в список-результат, устанавливаем бит в единицу. 4) возвращаем список-результат. количество операций равно количеству элементов, но на обнуление множества при больших числах элементов уйдет порядочно времени. Т.е. это неэффективно использовать для 3х..4х чисел int32, например. Для других/емких типов данных просто нужно замену битовой карте, принцип будет тот же. Ну а если это не подходит, то останется только "сортировка, затем перебор подряд". -- We are all going to hell and I'm driving the bus Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2007, 11:54 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
вот примерно так можно сделать деревьями - можно добавить поле и считать в него сколько раз встретился тот или иной элемент. сложность получится чтото вроде n*log2(n)/2 - от нее уже сложно уйти будет суть в том чтобы избежать линейного поиска в твоем внутреннем цикле можно не строить дерево просто на объектах - в любом языке есть сейчас классы типо Vector и тп, в которых уже есть быстрая реализация бинарного поиска и тп - лучше их юзать на самом деле если это пишется на каком-нибудь интерпретируемом языке, то действительно быстрее будет посортировать кьюсортом который там скомпилирован Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. _______________________________________ 2pro4U ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2007, 13:31 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Можете подсказать подобный поиск только на паскале? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 07:42 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Javascript (ECMAScript 5): Код: javascript 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:10 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
po4talyon, Надо бегать по спискам и добавлять в хэш-таблицу по критерию сравнения. Это будет O(N1+N2) формально, фактически немного медленнее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:13 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Хотя что-то хрень я написал. Можно даже так: Код: javascript 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:21 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Division X, для repeated правильнее использовать не массив, а объект. ------------- а вообще, забавно. ТС задал вопрос 4 года назад, вопрос решили. doubleich-11 сейчас попросил то же, но на Паскале. Ну и последовали ответы, в духе форума ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:25 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Яростный Мечдля repeated правильнее использовать не массив, а объект. А эффективнее - массив. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:28 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Division XЯростный Мечдля repeated правильнее использовать не массив, а объект. А эффективнее - массив.с массивом получаем О(N^2), а с объектом - О(N*lg(N)) (это если в движке объект реализован как дерево, если как хэштаблица, то другое, но явно меньше, чем поиск в массиве) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:33 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Яростный Меч, В-первых, объем массива repeated в наихудшем случае (каждый элемент повторяется ровно два раза) получается ровно половина исходного, т.е. сложность уже падает вдвое. Во вторых, объекты реализованы как хэши. В-третьих, как потом обрабатывать результаты без портянок кода? ForEach и map для объекта не сделаешь, в отличие от массива. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:38 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Division X, а, понял, repeated - это для результата. всё равно я бы с доп. объектом сделал: Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 15:48 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Яростный Меч, Хм. Тоже вариант: Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.05.2012, 16:38 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.05.2012, 23:04 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Чтобы быстро найти все похожие элементы массива, надо его отсортировать. После чего поиск будет очень быстрым. Если сотритровку учитывать, то нужен самый лучший алгоритм сортировки ). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2012, 09:54 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
Лучший алгоритм сортировки должен учитывать скорость обращения к элементу и количество элементов.. исходя из этого он Разбивает все множество сортировки на N Групп внутри которых идет сортировка методом пузырька. Потом группы группируются в P больщих групп внутри которых идет сортировка методом сортировки уже отсортированных групп ну и так далее ). П.С. Ясно, что метод пузырька в одного огромной группе не эффективен. Для определения размеров групп используются логарифмы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2012, 11:30 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
TVA_11Чтобы быстро найти все похожие элементы массива, надо его отсортировать. После чего поиск будет очень быстрым. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. отсортируй пожалуйста массив объектов типа Foo. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2012, 11:35 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
k0rvin, Самый простой метод сортировки по наименованию. Строка(Foo &x) > Строка(Foo &Y) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2012, 11:43 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
k0rvin, Если имеется ввиду, что Возможно Foo &x = Foo &y Foo &x <> Foo &y Невозможно Foo &x > Foo &y Foo &x < Foo &y ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2012, 11:46 |
|
||
|
самый эффективный алгоритм поиска одинаковых элементов списка
|
|||
|---|---|---|---|
|
#18+
TVA_11Лучший алгоритм сортировки должен учитывать скорость обращения к элементу и количество элементов.. исходя из этого он Разбивает все множество сортировки на N Групп внутри которых идет сортировка методом пузырька. Потом группы группируются в P больщих групп внутри которых идет сортировка методом сортировки уже отсортированных групп ну и так далее ). П.С. Ясно, что метод пузырька в одного огромной группе не эффективен. Для определения размеров групп используются логарифмы.Хоар, Шелл и прочие прошли мимо Вас? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2012, 12:06 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=37793367&tid=1342260]: |
0ms |
get settings: |
9ms |
get forum list: |
17ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
190ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
57ms |
get tp. blocked users: |
2ms |
| others: | 233ms |
| total: | 527ms |

| 0 / 0 |
