powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Подскажите самые быстрые коллекции
25 сообщений из 42, страница 1 из 2
Подскажите самые быстрые коллекции
    #39176236
Alexander_fx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
привет
Работаю с биржевыми данными
данных много - 30 000 000 экземпляров записей
в каждом экземпляре есть поле - цена - тип Double
необходимо иметь быстрый доступ к экземпляру по цене
dictionary of double на мой взгляд работает медленно
подскажите есть ли что то быстрее
может есть специализированные библиотеки сторонних производителей.
или может кто то видел библиотеки для работы с большими обьемами данных.
Спасибо.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176247
L.Otujktd
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Alexander_fx,
Ограничение по используемой памяти есть ?
Чтение будет последовательным или произвольным?
Я бы привязывал не к цене а к диапазонам цен, но нужно понять распределение по ценам.
Я так понимаю для целей производительности нужно узкоспециализированное решение...
Ну и нужно тест использования алгоритма для определения прироста производительности.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176252
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alexander_fx,

секционируй
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176260
Alexander_fx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L.Otujktd,

памяти много - готовы жертвовать памятью в угоду скорости.
чтение произвольное - заполнение массива тоже произвольное
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176261
Alexander_fx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRosAlexander_fx,

секционируй

а что это даст в плане скорости?
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176266
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
в данном случае я бы рекомендовал AVL-дерево.
Если биржевые данные, то количество позиций после запятой ограничено, Double не нужен.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176269
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
или пользуйтесь inmemory db, например extremedb или kdb+. Бесплатных аналогов не знаю
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176275
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alexander_fxпривет
в каждом экземпляре есть поле - цена - тип Double

Double неточный тип, его нельзя сравнивать, может просто не найтись. Например при цене 10,30 может оказаться 10,30000000001 != 10,30000000002

Используй Decimal, а лучше перевести в копейки и UInt32 или UInt64 если разрядности UInt32 не хватает.

Вообще тут сортированный по цене массив уместнее, но смотря как он меняется, если постоянно то лучше dictionary
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176277
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Самое быстрое и неэффективное по памяти - биткарта. Т.е. делаешь массив где цена индекс массива (не dictionary, а просто массив) но тут зависит от диапазона цен. Например если цена в диапазоне 20.00-30.00, то тебе потребуется 1000 элементов массива (20.00, 20.01 и т.д.) независимо от количества значений внутри. Т.е. для поиска надо будет вычислить (value - 20.00) * 100 и получишь индекс нужного элемента. Если диапазон 20.00-2000.00 это уже 198000 элементов.

Алгоритм сложности О(1), т.е. находится все с первого шага. Если памяти хватит.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176285
L.Otujktd
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Я так понимаю для фиксированного набора из 30*10^6 записей меняется только цена?
Т.е. основная задача в поиске схожих записей с одинаковым полем Price(выборка по полю)?
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176288
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L.OtujktdЯ так понимаю для фиксированного набора из 30*10^6 записей меняется только цена?
Т.е. основная задача в поиске схожих записей с одинаковым полем Price(выборка по полю)?
я так понимаю что Dictionary<Price> не может хранить два одинаковых Price
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176292
L.Otujktd
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dima T, очень мало вводной информации по поставленной задаче. А так по описанию тянет на полноценный сервис по поиску, обновлению данных в таблице фиксированного размера.:)
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176341
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я думаю что good enough будет цену в копейки и словарь по инту с распараллеливанием алгоритма по возможности.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176365
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Denis.Я думаю что good enough будет цену в копейки и словарь по инту с распараллеливанием алгоритма по возможности.
Какие копейки? Там торгуются инструменты с 4-5 знаков после запятой ))) поэтому словарь - не лучшее решение.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176369
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Можно еще прикинуть, сколько уникальных цен в этом массиве, и сделать битовую маску с разрядностью, равной порядку этого количества. А саму цену переводить в bigint с умножением на 10^5 и использовать ее остаток от деления нацело (используя тот же порядок).

Наверное, это будет самый быстрый доступ к точному значению цены, то если нужна будет выборка по диапазону - толку не будет
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176373
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Arm79Denis.Я думаю что good enough будет цену в копейки и словарь по инту с распараллеливанием алгоритма по возможности.
Какие копейки? Там торгуются инструменты с 4-5 знаков после запятой ))) поэтому словарь - не лучшее решение.
Int32 это 4 млрд. значений. 9 знаков. Если его хватит, то массив не такой уж и большой будет, при 32-64 Гб оперативки вполне может в памяти уместится.

Я так понял ищется лучшее решение по производительности, остальное не в счет. Массив, с ценой вместо индекса, самое быстрое решение, быстрее невозможно. И параллелить тут нечего.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176377
Arm79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TЕсли его хватит, то массив не такой уж и большой будет, при 32-64 Гб оперативки вполне может в памяти уместится.
Проблема в том, что ТС немножко недооценил широту души форумчан, которые и террабайт в оперативку могут запихнуть. А данных там поболее будет, чем 64Гб. Если на каждый чих создавать по 15Гб индекс, то памяти не хватит.

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

А так мое мнение, если позволяют финансы, - использовать in-memory СУБД в виде dll, подключаемой к программе

Ну и можно попробовать использовать Tarantool
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176383
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Arm79Dima TЕсли его хватит, то массив не такой уж и большой будет, при 32-64 Гб оперативки вполне может в памяти уместится.
Проблема в том, что ТС немножко недооценил широту души форумчан, которые и террабайт в оперативку могут запихнуть. А данных там поболее будет, чем 64Гб. Если на каждый чих создавать по 15Гб индекс, то памяти не хватит.

Arm79Массив можно уменьшить, если выбрать нормальную хэширующую функцию, вариант я предложил.
AVL-деревья также дают очень быстрый поиск, хотя и не О(1)

А так мое мнение, если позволяют финансы, - использовать in-memory СУБД в виде dll, подключаемой к программе

Ну и можно попробовать использовать Tarantool
Dictionary использует хэш-таблицу. Т.е. уже наиболее оптимальный вариант.
Надо затестить насколько тормознее массива.

Тут надо задачу предметнее изучать. Из-за чего именно тормоза. Например если из-за большого количества промахов, т.е. искомое отсутствует, тогда можно биткарту или фильтр Блума применить для предварительной оценки стоит ли искать.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176385
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Arm79которые и террабайт в оперативку могут запихнуть
не вижу проблем с терабайтом (24 планки по 64GB - не требуют космических технологий)
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176394
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
мне кажется что такого решения должно хватать. Если нет, то, возможно, вообще не та среда выбрана.
Если видеть точнее контекст можно делать вариации
Код: 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.
  internal sealed class Program
    {
        private const int NUMBERS_COUNT = 30 * 1000 * 1000;
        private static readonly Random randomizer = new Random();

        private static void Main()
        {
            var items = new Item[NUMBERS_COUNT];

            for (var i = 0; i < items.Length; i++)
                items[i] = new Item(randomizer.NextDouble(), string.Empty);

            var dict = new Dictionary<long, List<Item>>();
            foreach (var item in items)
            {
                var key = BitConverter.DoubleToInt64Bits(item.Price);
                List<Item> outItems;
                if (!dict.TryGetValue(key, out outItems))
                {
                    outItems = new List<Item>();
                    dict.Add(key, outItems);
                }
                outItems.Add(item);
            }

            foreach (var value in dict.Values)
                value.TrimExcess();

            //consumme in paralel
            // Parallel.ForEach()
        }

        private sealed class Item
        {
            public Item(double price, string someOtherStuff)
            {
                Price = price;
                SomeOtherStuff = someOtherStuff;
            }

            public double Price { get; }
            public string SomeOtherStuff { get; }
        }
    }
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176396
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
837ms на 20 000 000 элементов
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
...
   int t = Environment.TickCount;
            Parallel.ForEach(dict.Keys, (key) =>
            {
                bool b = dict.ContainsKey(key);
            });
            t = Environment.TickCount - t;
            Console.WriteLine(t);
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176397
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
если распараллелить чанками наверняка будет быстрее
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176434
Фотография Axeleron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alexander_fxпривет
Работаю с биржевыми данными
данных много - 30 000 000 экземпляров записей
в каждом экземпляре есть поле - цена - тип Double
необходимо иметь быстрый доступ к экземпляру по цене
dictionary of double на мой взгляд работает медленно
подскажите есть ли что то быстрее
может есть специализированные библиотеки сторонних производителей.
или может кто то видел библиотеки для работы с большими обьемами данных.
Спасибо.
Поверьте, не нужны Вам быстрые коллекции. Выбросьте свою программу с типом данных double для поля цена.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176438
Alexander_fx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Всем привет и спасибо за интересное обсуждение.

Пока склоняюсь к бит карте.
диапазон рабочих цен 100 000 экземпляров - так что биткарта не такая уж и большая.
смущало то что в этом диапазоне много разряженностей которые в пустую тратят память но есть большой плюс доступ к элементу по индексу.
...
Рейтинг: 0 / 0
Подскажите самые быстрые коллекции
    #39176498
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alexander_fxсмущало то что в этом диапазоне много разряженностей которые в пустую тратят память но есть большой плюс доступ к элементу по индексу.
Ты уж определись: быстро или экономно. Если все не влазит в 16-32 Кб (кэш проца), то можно смело размазывать по всей оперативке.

Биткарта на 100000 элементов 12,5 кб. Если добьешься чтобы остальное ее не вытесняло ее из кэша проца, то будет в 2-3 раза быстрее, чем постоянное обращение к памяти.
...
Рейтинг: 0 / 0
25 сообщений из 42, страница 1 из 2
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Подскажите самые быстрые коллекции
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]