|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
привет Работаю с биржевыми данными данных много - 30 000 000 экземпляров записей в каждом экземпляре есть поле - цена - тип Double необходимо иметь быстрый доступ к экземпляру по цене dictionary of double на мой взгляд работает медленно подскажите есть ли что то быстрее может есть специализированные библиотеки сторонних производителей. или может кто то видел библиотеки для работы с большими обьемами данных. Спасибо. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 18:07 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fx, Ограничение по используемой памяти есть ? Чтение будет последовательным или произвольным? Я бы привязывал не к цене а к диапазонам цен, но нужно понять распределение по ценам. Я так понимаю для целей производительности нужно узкоспециализированное решение... Ну и нужно тест использования алгоритма для определения прироста производительности. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 18:27 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fx, секционируй ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 18:29 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
L.Otujktd, памяти много - готовы жертвовать памятью в угоду скорости. чтение произвольное - заполнение массива тоже произвольное ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 18:41 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
ViPRosAlexander_fx, секционируй а что это даст в плане скорости? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 18:41 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
в данном случае я бы рекомендовал AVL-дерево. Если биржевые данные, то количество позиций после запятой ограничено, Double не нужен. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 18:50 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
или пользуйтесь inmemory db, например extremedb или kdb+. Бесплатных аналогов не знаю ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 18:52 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fxпривет в каждом экземпляре есть поле - цена - тип Double Double неточный тип, его нельзя сравнивать, может просто не найтись. Например при цене 10,30 может оказаться 10,30000000001 != 10,30000000002 Используй Decimal, а лучше перевести в копейки и UInt32 или UInt64 если разрядности UInt32 не хватает. Вообще тут сортированный по цене массив уместнее, но смотря как он меняется, если постоянно то лучше dictionary ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 19:09 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Самое быстрое и неэффективное по памяти - биткарта. Т.е. делаешь массив где цена индекс массива (не dictionary, а просто массив) но тут зависит от диапазона цен. Например если цена в диапазоне 20.00-30.00, то тебе потребуется 1000 элементов массива (20.00, 20.01 и т.д.) независимо от количества значений внутри. Т.е. для поиска надо будет вычислить (value - 20.00) * 100 и получишь индекс нужного элемента. Если диапазон 20.00-2000.00 это уже 198000 элементов. Алгоритм сложности О(1), т.е. находится все с первого шага. Если памяти хватит. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 19:17 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Я так понимаю для фиксированного набора из 30*10^6 записей меняется только цена? Т.е. основная задача в поиске схожих записей с одинаковым полем Price(выборка по полю)? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 19:59 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
L.OtujktdЯ так понимаю для фиксированного набора из 30*10^6 записей меняется только цена? Т.е. основная задача в поиске схожих записей с одинаковым полем Price(выборка по полю)? я так понимаю что Dictionary<Price> не может хранить два одинаковых Price ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 20:04 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Dima T, очень мало вводной информации по поставленной задаче. А так по описанию тянет на полноценный сервис по поиску, обновлению данных в таблице фиксированного размера.:) ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2016, 20:16 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Я думаю что good enough будет цену в копейки и словарь по инту с распараллеливанием алгоритма по возможности. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 01:24 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Denis.Я думаю что good enough будет цену в копейки и словарь по инту с распараллеливанием алгоритма по возможности. Какие копейки? Там торгуются инструменты с 4-5 знаков после запятой ))) поэтому словарь - не лучшее решение. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 11:21 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Можно еще прикинуть, сколько уникальных цен в этом массиве, и сделать битовую маску с разрядностью, равной порядку этого количества. А саму цену переводить в bigint с умножением на 10^5 и использовать ее остаток от деления нацело (используя тот же порядок). Наверное, это будет самый быстрый доступ к точному значению цены, то если нужна будет выборка по диапазону - толку не будет ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 11:35 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Arm79Denis.Я думаю что good enough будет цену в копейки и словарь по инту с распараллеливанием алгоритма по возможности. Какие копейки? Там торгуются инструменты с 4-5 знаков после запятой ))) поэтому словарь - не лучшее решение. Int32 это 4 млрд. значений. 9 знаков. Если его хватит, то массив не такой уж и большой будет, при 32-64 Гб оперативки вполне может в памяти уместится. Я так понял ищется лучшее решение по производительности, остальное не в счет. Массив, с ценой вместо индекса, самое быстрое решение, быстрее невозможно. И параллелить тут нечего. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 12:06 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Dima TЕсли его хватит, то массив не такой уж и большой будет, при 32-64 Гб оперативки вполне может в памяти уместится. Проблема в том, что ТС немножко недооценил широту души форумчан, которые и террабайт в оперативку могут запихнуть. А данных там поболее будет, чем 64Гб. Если на каждый чих создавать по 15Гб индекс, то памяти не хватит. Массив можно уменьшить, если выбрать нормальную хэширующую функцию, вариант я предложил. AVL-деревья также дают очень быстрый поиск, хотя и не О(1) А так мое мнение, если позволяют финансы, - использовать in-memory СУБД в виде dll, подключаемой к программе Ну и можно попробовать использовать Tarantool ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 12:28 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Arm79Dima TЕсли его хватит, то массив не такой уж и большой будет, при 32-64 Гб оперативки вполне может в памяти уместится. Проблема в том, что ТС немножко недооценил широту души форумчан, которые и террабайт в оперативку могут запихнуть. А данных там поболее будет, чем 64Гб. Если на каждый чих создавать по 15Гб индекс, то памяти не хватит. Arm79Массив можно уменьшить, если выбрать нормальную хэширующую функцию, вариант я предложил. AVL-деревья также дают очень быстрый поиск, хотя и не О(1) А так мое мнение, если позволяют финансы, - использовать in-memory СУБД в виде dll, подключаемой к программе Ну и можно попробовать использовать Tarantool Dictionary использует хэш-таблицу. Т.е. уже наиболее оптимальный вариант. Надо затестить насколько тормознее массива. Тут надо задачу предметнее изучать. Из-за чего именно тормоза. Например если из-за большого количества промахов, т.е. искомое отсутствует, тогда можно биткарту или фильтр Блума применить для предварительной оценки стоит ли искать. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 13:07 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Arm79которые и террабайт в оперативку могут запихнуть не вижу проблем с терабайтом (24 планки по 64GB - не требуют космических технологий) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 13:12 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
мне кажется что такого решения должно хватать. Если нет, то, возможно, вообще не та среда выбрана. Если видеть точнее контекст можно делать вариации Код: c# 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. 44.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 13:50 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
837ms на 20 000 000 элементов Код: c# 1. 2. 3. 4. 5. 6. 7. 8.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 14:07 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
если распараллелить чанками наверняка будет быстрее ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 14:08 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fxпривет Работаю с биржевыми данными данных много - 30 000 000 экземпляров записей в каждом экземпляре есть поле - цена - тип Double необходимо иметь быстрый доступ к экземпляру по цене dictionary of double на мой взгляд работает медленно подскажите есть ли что то быстрее может есть специализированные библиотеки сторонних производителей. или может кто то видел библиотеки для работы с большими обьемами данных. Спасибо. Поверьте, не нужны Вам быстрые коллекции. Выбросьте свою программу с типом данных double для поля цена. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 16:20 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Всем привет и спасибо за интересное обсуждение. Пока склоняюсь к бит карте. диапазон рабочих цен 100 000 экземпляров - так что биткарта не такая уж и большая. смущало то что в этом диапазоне много разряженностей которые в пустую тратят память но есть большой плюс доступ к элементу по индексу. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 16:32 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fxсмущало то что в этом диапазоне много разряженностей которые в пустую тратят память но есть большой плюс доступ к элементу по индексу. Ты уж определись: быстро или экономно. Если все не влазит в 16-32 Кб (кэш проца), то можно смело размазывать по всей оперативке. Биткарта на 100000 элементов 12,5 кб. Если добьешься чтобы остальное ее не вытесняло ее из кэша проца, то будет в 2-3 раза быстрее, чем постоянное обращение к памяти. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2016, 19:09 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fx, 1. Проверить / показать народу как обьявлен "dictionary of double". заменить на Dictionary<double, X>. 2. Собрать статистику <хэш, кол-во елементов>, как часто проиходит колизия. И показать здесь. 3. При создании словаря указать сразу его вместимость. 3*10^7 * 1.4 4. Создать словарь со собственной функцией хэша и сравнения. В функциях сравнение убрать/не далатаь проверку NaN. 5. быстрее словаря только массивы. Можно ускориться ими при определённых условия. но нужно больше информации. P.S. Не часто встретиш потребность словаря с вещественным ключём. Автор, уваж любопытство, зачем? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2016, 17:09 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
mikronAlexander_fx, 1. Проверить / показать народу как обьявлен "dictionary of double". заменить на Dictionary<double, X>. 2. Собрать статистику <хэш, кол-во елементов>, как часто проиходит колизия. И показать здесь. 3. При создании словаря указать сразу его вместимость. 3*10^7 * 1.4 4. Создать словарь со собственной функцией хэша и сравнения. В функциях сравнение убрать/не далатаь проверку NaN. 5. быстрее словаря только массивы. Можно ускориться ими при определённых условия. но нужно больше информации. P.S. Не часто встретиш потребность словаря с вещественным ключём. Автор, уваж любопытство, зачем? ТС пишет: "Работаю с биржевыми данными данных много — 30 000 000 экземпляров записей в каждом экземпляре есть поле — цена — тип Double необходимо иметь быстрый доступ к экземпляру по цене dictionary of double на мой взгляд работает медленно подскажите есть ли что то быстрее может есть специализированные библиотеки сторонних производителей. или может кто то видел библиотеки для работы с большими обьемами данных. ." ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2016, 17:44 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Winnipuh, Я вобще-то читать умею, а вот представить себе не могу. зачем мне знать то у нас по цене 2.54? Предположим - картошка, чудесно. А вдруг лук тоже по 2.54. Он нам уже не нужен? А почему не нужен а картошка нужна? А если картошка по 2.53 то нам уже точно нужен лук? Я могу ещё представить задачу: найти все продукт с максимальной ценой не больше заданной. А вот с задахей автора нихего представить не могу. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2016, 17:53 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Скорее всего это он неправильно сформулировал постановку задачи для сбора стакана заявок. Там, помимо цены, ключом выступает финансовый инструмент. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2016, 17:57 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
mikronWinnipuh, Я вобще-то читать умею, а вот представить себе не могу. зачем мне знать то у нас по цене 2.54? Предположим - картошка, чудесно. А вдруг лук тоже по 2.54. Он нам уже не нужен? А почему не нужен а картошка нужна? А если картошка по 2.53 то нам уже точно нужен лук? Я могу ещё представить задачу: найти все продукт с максимальной ценой не больше заданной. А вот с задахей автора нихего представить не могу. я хотел помочь людям ии занес с другого форума. мне вот интересно: вещественные числа могут храниться в каком-то виде вместо 2.45 будет 2.4499999999999 и как искать? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2016, 18:12 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
WinnipuhmikronWinnipuh, Я вобще-то читать умею, а вот представить себе не могу. зачем мне знать то у нас по цене 2.54? Предположим - картошка, чудесно. А вдруг лук тоже по 2.54. Он нам уже не нужен? А почему не нужен а картошка нужна? А если картошка по 2.53 то нам уже точно нужен лук? Я могу ещё представить задачу: найти все продукт с максимальной ценой не больше заданной. А вот с задахей автора нихего представить не могу. я хотел помочь людям ии занес с другого форума. мне вот интересно: вещественные числа могут храниться в каком-то виде вместо 2.45 будет 2.4499999999999 и как искать? вещественные нужно искать с заданной степенью погрешности Пример из МСДН: Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
Поэтому-то и предложили заменить на decimal или предварительно умножать на 10000 и хранить как Int64 ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2016, 18:44 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Arm79вещественные нужно искать с заданной степенью погрешности Пример из МСДН: Денежные значения нужно хранить в decimal... ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2016, 19:02 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
AxeleronДенежные значения нужно хранить в decimal... А денежные знаки в банке. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.02.2016, 11:03 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
mikronAxeleronДенежные значения нужно хранить в decimal... А денежные знаки в банке. Если есть таковые. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.02.2016, 12:39 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Axeleronmikronпропущено... А денежные знаки в банке. Если есть таковые. причем, при условии, если есть и те , и другие ... |
|||
:
Нравится:
Не нравится:
|
|||
23.02.2016, 12:44 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
mikronAlexander_fx, 1. Проверить / показать народу как обьявлен "dictionary of double". заменить на Dictionary<double, X>. 2. Собрать статистику <хэш, кол-во елементов>, как часто проиходит колизия. И показать здесь. 3. При создании словаря указать сразу его вместимость. 3*10^7 * 1.4 4. Создать словарь со собственной функцией хэша и сравнения. В функциях сравнение убрать/не далатаь проверку NaN. 5. быстрее словаря только массивы. Можно ускориться ими при определённых условия. но нужно больше информации. P.S. Не часто встретиш потребность словаря с вещественным ключём. Автор, уваж любопытство, зачем? 2- подскажите плиз как собрать данную статистику p.s. - полностью согласен что double тут типиковая ветвь - буду переходить на int . ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2016, 21:38 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fxсмущало то что в этом диапазоне много разряженностей которые в пустую тратят память но есть большой плюс доступ к элементу по индексу.Посмотрите в сторону LinkedHashMap . По сути это HashMap + Linked Key List. К сожалению, аналога в .NET не существует. Но есть пример реализации: NHibernate.Util.LinkedHashMap . ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2016, 01:57 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
UsmanAlexander_fxсмущало то что в этом диапазоне много разряженностей которые в пустую тратят память но есть большой плюс доступ к элементу по индексу.Посмотрите в сторону LinkedHashMap . По сути это HashMap + Linked Key List. К сожалению, аналога в .NET не существует. Но есть пример реализации: NHibernate.Util.LinkedHashMap . а какие там преимущества? Код: c# 1. 2. 3. 4. 5.
по моему там обычная коллекция с обёрткой Entry, TValue значение которой находится в Value свойство Entry. по моему по скорости работать будет так же как и обычный Dictionary ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2016, 08:39 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Roman Mejtesа какие там преимущества?Фишка в том, что ключи хранятся в порядке добавления в коллекцию. Т.о. избавляемся от разряженностей и при этом имеем доступ к элементу по индексу. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2016, 11:20 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
Alexander_fxmikronAlexander_fx, 2. Собрать статистику <хэш, кол-во елементов>, как часто проиходит колизия. И показать здесь. 3. При создании словаря указать сразу его вместимость. 3*10^7 * 1.4 4. Создать словарь со собственной функцией хэша и сравнения. В функциях сравнение убрать/не далатаь проверку NaN. 5. быстрее словаря только массивы. Можно ускориться ими при определённых условия. но нужно больше информации. 2- подскажите плиз как собрать данную статистику И вобоще, кто с биржевыми данными работает и сам может статиску собрать. Код: c# 1. 2. 3. 4. 5. 6. 7. 8.
... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2016, 12:22 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
тогда уж так Код: c# 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2016, 22:22 |
|
Подскажите самые быстрые коллекции
|
|||
---|---|---|---|
#18+
ну а вообще если инты с ценами то вообще халява у цен обычно маленький диапазон. Конвертишь в инты с заданной точностью, ищешь мин значение, это будет дельта, далее просто массив списков(если есть коллизии) где индекс это цена минус дельта ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2016, 22:25 |
|
|
start [/forum/topic.php?all=1&fid=20&tid=1400777]: |
0ms |
get settings: |
11ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
46ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
77ms |
get tp. blocked users: |
1ms |
others: | 286ms |
total: | 456ms |
0 / 0 |