Здравствуйте, какое-то время назад написал свой контейнер, специально приспособленный для хранения больших объемов данных, для которых List и LinkedList будут работать крайне неэффективно. Например при вставке в середину List'a с 10к элементов нам придется сдвинуть "вправо" 5к элементов, если вообще не случиться переполнения(если capacity == 10к) и не придется выделять новую память. Старался соблюсти разумный компромисс между скоростью и требованию к памяти.

Единственный найденный мною аналог — библиотека PowerCollections(а именно элемент BigList) от дяди Рихтера(вернее его компании) не понравилась ввиду сильного проседания во многих местах. Например, заполнение коллекции из 10^5 с середины:

for(int i=0;i<10000;i++)
{
   collection.Insert(collection.Count/2, i);
}

у меня происходит за 120 мсек, у дяди Рихтера за 15 сек.
Или следующий код в массиве из 10^4 элементов:

for (int i = 0; i < 10000; i++)
{
   collection.IndexOf(i);
}

у меня выполняется за 60 мсек, у дяди Рихтера за 2 сек.
Конечно, далеко не везде удалось достичь таких результатов, но вроде бы удалось достичь того, чтобы нигде не было таких сильных мест проседания(насколько это возможно).
Если вы думаете, что это за счет оперативной памяти, то процесс с коллекцией из 10 миллионов(10^7) int'ов, заполненных в цикле с помощью Add() у ДР берет 67.1 мб, а у меня 48.7

Не хотелось бы сейчас все обрисовать куда лучше, чем есть на самом деле, поэтому если интересно сама библиотека здесь, в виде dll занимает всего около 30 кб.

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

P.S> изначально расположил пост тут: http://www.rsdn.ru/forum/src/ , но вскоре увидел, что эта ветка форума практически мертва, поэтому извините за такой косяк и если можно удалите её оттуда.

Здравствуйте, 80LevelElf, Вы писали:

LE>Здравствуйте, какое-то время назад написал свой контейнер, специально приспособленный для хранения больших объемов данных, для которых List и LinkedList будут работать крайне неэффективно. Например при вставке в середину List'a с 10к элементов нам придется сдвинуть "вправо" 5к элементов, если вообще не случиться переполнения(если capacity == 10к) и не придется выделять новую память. Старался соблюсти разумный компромисс между скоростью и требованию к памяти.

LE>Единственный найденный мною аналог — библиотека PowerCollections(а именно элемент BigList) от дяди Рихтера(вернее его компании) не понравилась ввиду сильного проседания во многих местах. Например, заполнение коллекции из 10^5 с середины:


LE>

LE>for(int i=0;i<10000;i++)
LE>{
LE>   collection.Insert(collection.Count/2, i);
LE>}
LE>

LE>у меня происходит за 120 мсек, у дяди Рихтера за 15 сек.
LE>Или следующий код в массиве из 10^4 элементов:

LE>

LE>for (int i = 0; i < 10000; i++)
LE>{
LE>   collection.IndexOf(i);
LE>}
LE>

LE>у меня выполняется за 60 мсек, у дяди Рихтера за 2 сек.
LE>Конечно, далеко не везде удалось достичь таких результатов, но вроде бы удалось достичь того, чтобы нигде не было таких сильных мест проседания(насколько это возможно).
LE>Если вы думаете, что это за счет оперативной памяти, то процесс с коллекцией из 10 миллионов(10^7) int'ов, заполненных в цикле с помощью Add() у ДР берет 67.1 мб, а у меня 48.7

LE>Не хотелось бы сейчас все обрисовать куда лучше, чем есть на самом деле, поэтому если интересно сама библиотека здесь, в виде dll занимает всего около 30 кб.

LE>К тому же если есть знающие люди, они наверняка найдут множество мест, где моя библиотека проигрывает ДР, да и не стоит забывать про качество нового проекта любителя и вылизанного годами проекта самого ДР.

P.S>> изначально расположил пост тут: http://www.rsdn.ru/forum/src/ , но вскоре увидел, что эта ветка форума практически мертва, поэтому извините за такой косяк и если можно удалите её оттуда.

Разобрался как удалить первую тему, еще раз прошу прощения за косячность.

LE>Не хотелось бы сейчас все обрисовать куда лучше, чем есть на самом деле, поэтому если интересно сама библиотека здесь, в виде dll занимает всего около 30 кб.

Странные названия. Под big data обычно несколько другое понимают, distributed подразумевает распределенность. Почему такие названия? Ну и интересно — какие структуры данных ты там реализовал?

Здравствуйте, Lazin, Вы писали:

LE>>Не хотелось бы сейчас все обрисовать куда лучше, чем есть на самом деле, поэтому если интересно сама библиотека здесь, в виде dll занимает всего около 30 кб.

L>Странные названия. Под big data обычно несколько другое понимают, distributed подразумевает распределенность. Почему такие названия? Ну и интересно — какие структуры данных ты там реализовал?

Названия, согласен, наверное не очень удачные. Изначально называл исходя из архитектуры самого контейнера. Ну а самих структур, как вы уже наверное сами видели раз смотрели код, всего 3: собственно сам DistributedArray(ядро так сказать) и построенный на его основе DistributedStack и DistributedQueue.

Здравствуйте, 80LevelElf, Вы писали:

LE>Здравствуйте, какое-то время назад написал свой контейнер, специально приспособленный для хранения больших объемов данных, для которых List и LinkedList будут работать крайне неэффективно. Например при вставке в середину List'a с 10к элементов нам придется сдвинуть "вправо" 5к элементов, если вообще не случиться переполнения(если capacity == 10к) и не придется выделять новую память. Старался соблюсти разумный компромисс между скоростью и требованию к памяти.

LE>Единственный найденный мною аналог — библиотека PowerCollections(а именно элемент BigList) от дяди Рихтера(вернее его компании) не понравилась ввиду сильного проседания во многих местах. Например, заполнение коллекции из 10^5 с середины:

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

Здравствуйте, VladiCh, Вы писали:

VC>Не понял что неэффективно с LinkedList?
конкретно линкидлист имеет безумно большой оферхед по памяти, если в нем например числа хранить

Здравствуйте, 80LevelElf, Вы писали:

https://github.com/80LevelElf/Bigio/blob/master/Bigio/BigArray/BigArray.cs#L223

IComparer<T>.Compare может вернуть любое число, а не -1/0/+1

Здравствуйте, Jack128, Вы писали:

J>Здравствуйте, 80LevelElf, Вы писали:

J>https://github.com/80LevelElf/Bigio/blob/master/Bigio/BigArray/BigArray.cs#L223

J>IComparer<T>.Compare может вернуть любое число, а не -1/0/+1

Ого как. Кто-то посмотрел мой код. Круто)
Да, вы правы — ошибся. Спасибо большое!

Здравствуйте, VladiCh, Вы писали:

VC>Не понял что неэффективно с LinkedList? Каждая структура данных имеет свое применение, если требуется много вставлять в середину коллекции, надо использовать или LinkedList или какое-нибудь дерево (опять же в зависимости от задачи).

Проблем много:
1) Очень много жрется памяти. На больших данных LinkedList не очень юзабелен. Это по-сути главная проблема.
2) Просто так, например, в середину вы не вставите — нужно пройти пол-списка, чтобы достигнуть этой позиции. Если в общем — нет индексации, а это не так уж удобно.

Вы абсолютно правы — для каждой задачи нужны свои инструменты. Обычные коллекции хороши для обычных данных(там тысяча или 10 тысяч элементов). Для чего-то большего они не приспособлены.

Дерево проблему с памятью и индексацией тоже не решит.