Всем привет,
Конструирую Key-Value структуру данных.
Поиск Log(1), Вставки Log(1)
Особенностью этой структуры есть черезвычайно высокая скорость поиска
(от 3,1 наносекунд до 50 нс занимает один поиск), высокая скорость вставок (от 5нс до 50 нс),
экономия памяти вплоть до компрессии данных,
возможность выборок по диапазону ключей (данные в структуре отсортированы).

Вопрос такой.
Что еще можно потестить из асоциативных массивов, может какая структура данных с со схожими параметрами
ускользнула из вида ?

Бенчмарки можно глянуть здесь
http://www.sql.ru/blogs/stebelek/1269

И здесь
http://www.sql.ru/blogs/stebelek/1267

Спасибо!

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

PC_>Поиск Log(1), Вставки Log(1)

O'RLY?
Log(1) = 0

Мнгновенный поиск-вставка?

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

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

PC_>>Поиск Log(1), Вставки Log(1)

__>O'RLY?
__>Log(1) = 0

__>Мнгновенный поиск-вставка?

Пардон, О(1)

ап

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

PC_>ап
Код где?

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

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

PC_>>ап
WH>Код где?

Код не опен сорц.
Опенсорснул я только одну из тестовых версий.
http://www.sql.ru/forum/actualfile.aspx?id=12509735

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

PC_>Поиск Log(1), Вставки Log(1)

Это, простихоспаде как?
Это за 0 операций вставляется и ищется? Срочно премию получать!

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

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

PC_>>Поиск Log(1), Вставки Log(1)

W>Это, простихоспаде как?
W>Это за 0 операций вставляется и ищется? Срочно премию получать!

Приятно, что в Эстонии тоже читают рсдн.

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

PC_>Конструирую Key-Value структуру данных.
PC_>Поиск Log(1), Вставки Log(1)
PC_>Особенностью этой структуры есть черезвычайно высокая скорость поиска
PC_>(от 3,1 наносекунд до 50 нс занимает один поиск), высокая скорость вставок (от 5нс до 50 нс),
PC_>экономия памяти вплоть до компрессии данных,
PC_>возможность выборок по диапазону ключей (данные в структуре отсортированы).

Протести
1. удаление
2. добавление 1 млн элементов
3. итерации по всему списку

Например hashset выдыхается на удалении, здесь у него O(N^^2) и все становится грустно.

PC_>Вопрос такой.
PC_>Что еще можно потестить из асоциативных массивов, может какая структура данных с со схожими параметрами
PC_>ускользнула из вида ?

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

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

PC_>Бенчмарки можно глянуть здесь
PC_>http://www.sql.ru/blogs/stebelek/1269

главное что бы расход памяти не был O(N^^2) Где, кстати расход памяти ?

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

I>Протести
I>1. удаление
I>2. добавление 1 млн элементов
I>3. итерации по всему списку

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

I>Например hashset выдыхается на удалении, здесь у него O(N^^2) и все становится грустно.

Попробуй протестировать hashset на вставки.

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

Нельзя, по памяти будет не оптимально для рандом значений.

PC_>>Бенчмарки можно глянуть здесь
PC_>>http://www.sql.ru/blogs/stebelek/1269
I>главное что бы расход памяти не был O(N^^2) Где, кстати расход памяти ?

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

Кстате, а о каком ХешСет речь ?
Этот хеш сет вроде не моделирует пары Ключ/Значение.

HashSet<int> d = new HashSet<int>();

Здравствуйте, PC_2

Сравните с Judy и Ternary Search Tree для поиска по строкам

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

R>Здравствуйте, PC_2

R>Сравните с Judy и Ternary Search Tree для поиска по строкам

Спасибо, только боюсь время займет скачать, настроить это все под виндовз, запустить.
Ни у кого случайно нет настроеной среды сделать простенький тест ?
Вставка/Поиск нескольких миллионов ключей.

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

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

R>>Здравствуйте, PC_2

R>>Сравните с Judy и Ternary Search Tree для поиска по строкам

PC_>Спасибо, только боюсь время займет скачать, настроить это все под виндовз, запустить.
PC_>Ни у кого случайно нет настроеной среды сделать простенький тест ?
PC_>Вставка/Поиск нескольких миллионов ключей.

Нашел врапер этой либы под дот нет https://github.com/dump247/JudyArray
После нескольких затяжных танцев с бубнами удалось завести сию либу.
Но результаты удручающи. В разы отстала от стандартного Dictionary.NET.
Конечно там еще обертка какойто перформенц отбирает, но не в разы же ...

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

Для сравнения, 1 млн рандом ключей.
Икор7
Вставка Джуди 1,1 секунда
Стандартный Диктионари 0,151 сек

Вставка Джуди 0,8 секунда
Стандартный Диктионари 0,142 сек

У меня для строк пока не запилина версия но для интов,
будет гдето 0,051 сек вставки
и 0,041 поиск

Код примерно такой

//fill
            List<string> keys = new List<string>();
            FileStream fs = new FileStream(@"c:\rand.bin", FileMode.Open);

            //JudyArray.JudyStringDictionary<int> judy = new JudyStringDictionary<int>();

            Dictionary<string, int> d = new Dictionary<string, int>(1000000);
            BinaryReader br = new BinaryReader(fs);
            for (int i = 0; i < 1000000; i++)
            {
                //keys.Add(br.ReadInt32());
                int num = br.ReadInt32();
                keys.Add(num.ToString());
            }

            br.Close();
            fs.Close();

            Stopwatch sw = new Stopwatch();
            sw.Start();

            //keys.Sort();

            for (int i = 0; i < keys.Count; i++)
            {
                //judy[keys[i]] = i;

                if (!d.ContainsKey(keys[i]))
                {
                    d.Add(keys[i], i);
                }
            }

            sw.Stop();

            MessageBox.Show(sw.ElapsedMilliseconds.ToString());

            sw = new Stopwatch();
            sw.Start();

            //keys.Sort();

            for (int i = 0; i < keys.Count; i++)
            {
                //judy.TryGetValue(keys[i], out value);
                if (d[keys[i]] != i)
                {
                    //MessageBox.Show("Error");
                }
                //if (!d.ContainsKey(keys[i]))
                //    d.Add(keys[i], keys[i]);
            }

            sw.Stop();

            MessageBox.Show(sw.ElapsedMilliseconds.ToString());

PC_>Всем привет,
PC_>Конструирую Key-Value структуру данных.
PC_>Поиск Log(1), Вставки Log(1)
PC_>Особенностью этой структуры есть черезвычайно высокая скорость поиска
PC_>(от 3,1 наносекунд до 50 нс занимает один поиск), высокая скорость вставок (от 5нс до 50 нс),
PC_>экономия памяти вплоть до компрессии данных,
PC_>возможность выборок по диапазону ключей (данные в структуре отсортированы).

Выделенное ставит под вопрос O(1) для вставки. Возможно, O(1) «амортизированный»?

Удаление из структуры все же очень интересует.

PC_>>Всем привет,
PC_>>Конструирую Key-Value структуру данных.

Прделагаю тему превентивно удалить. Предыстория тут: http://www.sql.ru/forum/actualthread.aspx?tid=863510

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

I>>Протести
I>>1. удаление
I>>2. добавление 1 млн элементов
I>>3. итерации по всему списку

PC_>Удаление я пока что не рассматривал,
PC_>поскольку большинство задач это Вставка и Поиск в хештаблице.
PC_>Удаление обычно ограничивается Clear.

Это и половины случаев не покроет.

I>>Например hashset выдыхается на удалении, здесь у него O(N^^2) и все становится грустно.

PC_>Попробуй протестировать hashset на вставки.

Так себе.

PC_>В колонке вроде есть расход памяти, тоже экономней расходует ...

Ну значит удаление умрёт наверняка

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

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

I>>>Протести
I>>>1. удаление
I>>>2. добавление 1 млн элементов
I>>>3. итерации по всему списку

PC_>>Удаление я пока что не рассматривал,
PC_>>поскольку большинство задач это Вставка и Поиск в хештаблице.
PC_>>Удаление обычно ограничивается Clear.

I>Это и половины случаев не покроет.

Ну а каких случаев ? Почему так важно удаление ?
В нашей рабочей СУБД данные удаляются очень редко, они просто архивируются и база живет дальше.
Также чтобы построить движок фул текст энжин, тоже удаление не нужно.
Чтобы посчитать количество уникальных значений, отсортировать чтото — удаление не нужно.
И так далее. Из операций Вставка/Поиск/Память/Удаление, само по себе Удаление менее всего интересно
как операция.

Но если интересно удаление, то пока происходит обычное разрежение структуры данных за О(1) время.
При разрежении может оказаться, что некоторые страницы памяти пусты. Они удаляются и тогда уже высвобождается память.
Структуру данных можно перестроить, чтото вроде шринка в обычных СУБД.

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

I>>Это и половины случаев не покроет.

PC_>Ну а каких случаев ? Почему так важно удаление ?

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

PC_>Но если интересно удаление, то пока происходит обычное разрежение структуры данных за О(1) время.
PC_>При разрежении может оказаться, что некоторые страницы памяти пусты. Они удаляются и тогда уже высвобождается память.
PC_>Структуру данных можно перестроить, чтото вроде шринка в обычных СУБД.

У тебя шота все за O(1), чтото не так с тестами. Код тестов ты не выкладывал ?