Выбрать диапазон ключей

Язык Visual Basic на платформе .NET.

Модераторы: Ramzes, Sebas

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Выбрать диапазон ключей

Сообщение kanut » 01.04.2013 (Пн) 19:44

Не смог найти как в VB можно выделить из коллекции определенный диапазон ключей. Например, есть коллекция Dictionary(Of Integer, Integer) с ключами 1, 2, 2.1, 2.1, 5, 7.5, 7.5, 9 и какими угодно значениями. Нужно выделить из нее все ключи от 2 до 7.9 не используя цикл, перебор всех ключей. Может есть такая специализированная функция в самом Framework?

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 01.04.2013 (Пн) 21:39

kanut писал(а):Например, есть коллекция Dictionary(Of Integer, Integer) с ключами 1, 2, 2.1, 2.1, 5, 7.5, 7.5, 9

Dictionary не может содержать совпадающих ключей. И числа у тебя не Integer.

kanut писал(а):Нужно выделить из нее все ключи от 2 до 7.9 не используя цикл, перебор всех ключей.

Нет, .NET не предоставляет такую возможность для классов SortedDictionary и, тем более, Dictionary.

Если такая задача действительно требует высокую производительность, то следует использовать другие способы хранения.

FireFenix
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1640
Зарегистрирован: 25.05.2007 (Пт) 10:24
Откуда: Mugen no Sora

Re: Выбрать диапазон ключей

Сообщение FireFenix » 02.04.2013 (Вт) 0:15

kanut писал(а):Нужно выделить из нее все ключи от 2 до 7.9 не используя цикл, перебор всех ключей

Если шаг ключей определённый, то в цикле можно перебрать килю от 2 с шагом N до 7.9. Но от этого будет профит, если ключей больше чем запрашиваемый диапазон, а так обычный перебор быстрее
Если не изменяет память, можно заюзать SortedList, первый элемент выбирать по ключу через IndexOfKey и дальше по индексам перебор, пока не > 7.9 (Производительность с перебором в лоб - не знаю)
Птицей Гермеса меня называют, свои крылья пожирая... сам себя я укрощаю
私はヘルメスの鳥 私は自らの羽根を喰らい 飼い慣らされる

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 6:39

FireFenix писал(а):Если шаг ключей определённый, то ...

... надо использовать массив :)

FireFenix писал(а):Но от этого будет профит, если ключей больше чем запрашиваемый диапазон, а так обычный перебор быстрее

?

FireFenix писал(а):Если не изменяет память, можно заюзать SortedList

Если не ошибаюсь, он является List'ом, соответственно производительность вставки и удаления в произвольные места будет плохой.

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 02.04.2013 (Вт) 10:02

Qwertiy писал(а):Dictionary не может содержать совпадающих ключей. И числа у тебя не Integer.


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

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

Если нет, тогда придется писать функцию выбора самому :( - деление пополам, сравнение, снова деление, снова сравнение и т.д.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 10:58

kanut писал(а):Странно, если действительно такой стандартной возможности нет.

Ты не описываешь ситуацию, поэтому нельзя ответить что именно нужно.

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 02.04.2013 (Вт) 11:52

Нужно, чтобы коллекция типа "ключ (возможно повторяющиеся числа, тип Double)-значение (возможно повторяющиеся числа, тип массив Double())" быстро возвращала один или несколько своих ключей (еще лучше просто начальный и конечный номера подходящих ключей в последовательности), удовлетворяющих минимальному и максимальному указанным значениям. Количество элементов в коллекции - до 1-10 миллионов и при этом выборка диапазона будет очень частой. Надо делать выборку максимально быстро для VB Net.

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 02.04.2013 (Вт) 12:01

Кстати, я не смог найти типа коллекций подобных List, но еще и со значениями, чтобы можно было добавлять повторяющиеся числа. Неужели таких нет? Тогда придется использовать одновременно две разных коллекции для ключей и значений и синхронно выполнять с ними действия?

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 12:30

Коллекция фиксированная или меняется? Если меняется, то что именно - ключи, значения или и то, и другое?

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 02.04.2013 (Вт) 12:34

Периодически будут добавляться новые пары ключ-значение. Те, элементы что уже есть не удаляются, не меняются.

FireFenix
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1640
Зарегистрирован: 25.05.2007 (Пт) 10:24
Откуда: Mugen no Sora

Re: Выбрать диапазон ключей

Сообщение FireFenix » 02.04.2013 (Вт) 12:36

Qwertiy писал(а):
FireFenix писал(а):Но от этого будет профит, если ключей больше чем запрашиваемый диапазон, а так обычный перебор быстрее?

Это же очевидно, если массив имеет диапазон ключей 0-100, а ты запрашиваешь 90-100, то профит перебора 10*[шаг перебора] ключей против 100.

kanut писал(а):Кстати, я не смог найти типа коллекций подобных List

Зачем другие коллекции если есть List? и более того есть SortedList!

kanut писал(а):Если нет, тогда придется писать функцию выбора самому :( - деление пополам, сравнение, снова деление, снова сравнение и т.д.

Перед этим идёт сортировка элементов не забывай. SortedList за тебя это сделает лучше

kanut писал(а):Нужно, чтобы коллекция типа "ключ (возможно повторяющиеся числа, тип Double)-значение (возможно повторяющиеся числа, тип массив Double())"

Вначале сформируйте задание, т.е. для чего вам это надо и почему именно коллекция вам нужна

kanut писал(а):быстро возвращала один или несколько своих ключей

Быстро это как? 100мс? 200мс? O(1)? O(n)?

kanut писал(а):Количество элементов в коллекции - до 1-10 миллионов и при этом выборка диапазона будет очень частой. Надо делать выборку максимально быстро для VB Net.

Какое-то наркоманство для работы с диапазонами. Для этого будет эффективнее использовать СУБД (если локально, то типа SQLite)
Птицей Гермеса меня называют, свои крылья пожирая... сам себя я укрощаю
私はヘルメスの鳥 私は自らの羽根を喰らい 飼い慣らされる

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 02.04.2013 (Вт) 13:15

FireFenix писал(а):Зачем другие коллекции если есть List? и более того есть SortedList!

Извиняюсь, я до этого думал, что List это сортированная коллекция, просто в нее можно добавлять одинаковые ключи и они будут идти подряд. Сейчас проверил, а они идут в порядке добавления... Значит коллекций с повторяющимися ключами в Framework нет.:? Тогда подходит только SortedDictionary(Of Double, List(Of Double)) и при добавлении ключа, который уже был в коллекции, буду запихивать массив (который предполагался сначала) в коллекцию List(). К счастью, количество элементов массива стандартное.

FireFenix писал(а):Быстро это как? 100мс? 200мс? O(1)? O(n)?

Намного быстрее перебора подряд, быстрейшим из доступных способов.

FireFenix писал(а):Для этого будет эффективнее использовать СУБД (если локально, то типа SQLite)

Лучше, если не найду стандартного средства в Framework, то сделаю функцию сам.

FireFenix
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1640
Зарегистрирован: 25.05.2007 (Пт) 10:24
Откуда: Mugen no Sora

Re: Выбрать диапазон ключей

Сообщение FireFenix » 02.04.2013 (Вт) 14:00

kanut писал(а):
FireFenix писал(а):Зачем другие коллекции если есть List? и более того есть SortedList!

Извиняюсь, я до этого думал, что List это сортированная коллекция, просто в нее можно добавлять одинаковые ключи и они будут идти подряд. Сейчас проверил, а они идут в порядке добавления... Значит коллекций с повторяющимися ключами в Framework нет.:? Тогда подходит только SortedDictionary(Of Double, List(Of Double)) и при добавлении ключа, который уже был в коллекции, буду запихивать массив (который предполагался сначала) в коллекцию List(). К счастью, количество элементов массива стандартное.

SortedList это смесь List + Dictionary. Имея индексы можно делать поиск хешу и перебирать потом диапазон индексов, но как и SortedDictionary при каждой вставке выполняется сравнение элемента с уже имеющимися в худшем случаю дающее O(log2 n), т.е. если на перебор всего массива требуется 200мс, то для вставки 100мс

Проблему одинаковых элементов можно решить добавив Массив на выходе с ключа. SortedList(Of Double, List(Of Double))

Преимущество SortedList над SortedDictionary это наличие Индексов, что позволяет ускорить поиск и не использовать любые виды переборов

kanut писал(а):
FireFenix писал(а):Быстро это как? 100мс? 200мс? O(1)? O(n)?

Намного быстрее перебора подряд, быстрейшим из доступных способов.

Очень информативный ответ...
Тогда почему вы уверены что перебор подряд очень долгая операция?

Чисто теоретически:
На одном ядре с частотой 3,3ГГц при отсутствии кеш-промаха и высоким приоритетом задачи получаем ~3млрд операций.
Перебор в цикле это 2х(cmp (x64 - 1, х86 - 3) + jmp) + inc + jmp ~ 10 инструкций.
Того мы получаем что ваши 10 миллионов записей будут обработаны за 1 /( 3млрд/ (10*10млн)) ~ 33,3мс.

kanut писал(а):
FireFenix писал(а):Для этого будет эффективнее использовать СУБД (если локально, то типа SQLite)

Лучше, если не найду стандартного средства в Framework, то сделаю функцию сам.

Лучше правильно поставить задачу и найти правильно решение, чего вы не делаете.
Последний раз редактировалось FireFenix 02.04.2013 (Вт) 14:39, всего редактировалось 1 раз.
Птицей Гермеса меня называют, свои крылья пожирая... сам себя я укрощаю
私はヘルメスの鳥 私は自らの羽根を喰らい 飼い慣らされる

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 14:18

FireFenix писал(а):Это же очевидно, если массив имеет диапазон ключей 0-100, а ты запрашиваешь 90-100, то профит перебора 10*[шаг перебора] ключей против 100.

А, это ты опять про ключи с заданным шагом...

FireFenix писал(а):Какое-то наркоманство для работы с диапазонами. Для этого будет эффективнее использовать СУБД (если локально, то типа SQLite)

Не говори фигню!

FireFenix писал(а):Быстро это как? 100мс? 200мс? O(1)? O(n)?

O(lb n) - очевидно же.

kanut писал(а):Тогда подходит только SortedDictionary(Of Double, List(Of Double))

Не подходит в соответствии с необходимостью быстро извлекать диапазоны ключей.

kanut писал(а):Лучше, если не найду стандартного средства в Framework, то сделаю функцию сам.

Так и надо.

FireFenix писал(а):SortedList это смесь List + Dictionary.

Не правда. SortedList - это List. Да он отсортирован, но при вставке минимального элемента всё сдвигается, выполняя O(n) действий.

FireFenix писал(а):Преимущество SortedList над SortedDictionary это наличие Индексов, что позволяет ускорить поиск и не использовать любые виды переборов

Да, обращение по индексду для SortedList O(1), поиск O(lb n).

FireFenix писал(а):Лучше правильно поставить задачу и найти правильно решение, чего вы не делаете.

Постепенно делает.

kanut писал(а):Периодически будут добавляться новые пары ключ-значение.

Насколько часто? Приемлимо ли выполнение O(n) действий при операции вставки?

kanut писал(а):Те, элементы что уже есть не удаляются, не меняются.

Это можно использовать.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 14:31

FireFenix писал(а):Проблему одинаковых элементов можно решить добавив Массив на выходе с ключа. SortedList(Of Double, List(Of Double))

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

FireFenix писал(а):Чисто теоретически:
На одном ядре с частотой 3,3ГГц при отсутствии кеш-промаха и высоким приоритетом задачи получаем ~3млрд операций.
Перебор в цикле это 2х(cmp (x64 - 1, х86 - 3) + jmp) + inc + jmp ~ 10 инструкций.
Того мы получаем что ваши 10 миллионов записей будут обработаны за 1 /( 3млрд/ (10*10млн)) ~ 33,3мс.

Это слишком "чисто теоретически". Операций намного больше даже на Си, а .NET такую скорость уж точно не даст. Куда ты все проверки валидности дел?

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 02.04.2013 (Вт) 14:44

FireFenix писал(а):SortedList это смесь List + Dictionary

Да, а я вначале подумал, что это List, просто сортированный

FireFenix писал(а):Тогда почему вы уверены что перебор подряд очень долгая операция?

:shock: :D
Это очевидно. За 33 мс мне нужно уже выбрать уйму диапазонов, а не перебрать 1 раз все элементы.

Кстати, 10 млн. записей это максимум, а начинаться коллекция будет с 1 элемента.

FireFenix
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1640
Зарегистрирован: 25.05.2007 (Пт) 10:24
Откуда: Mugen no Sora

Re: Выбрать диапазон ключей

Сообщение FireFenix » 02.04.2013 (Вт) 14:49

Qwertiy писал(а):
FireFenix писал(а):Какое-то наркоманство для работы с диапазонами. Для этого будет эффективнее использовать СУБД (если локально, то типа SQLite)

Не говори фигню!

Опять ты пристал. Человек не говорит зачем ему нужно, а так же возможно он использует массив для хранения индексного дерева некоторых элементов.
С учётом большого количества элементов, выборки диапазонов, сложных условий и удобности лучше использовать СУБД

Qwertiy писал(а):
FireFenix писал(а):Быстро это как? 100мс? 200мс? O(1)? O(n)?

O(lb n) - очевидно же.

У тебя развитая телепатия и ты знаешь, что для человека быстро?
И что за lb n? Может имелось ввиду log2 n?

Qwertiy писал(а):
FireFenix писал(а):SortedList это смесь List + Dictionary.

Не правда. SortedList - это List. Да он отсортирован, но при вставке минимального элемента всё сдвигается, выполняя O(n) действий.

И где тут не правда? я же не сказал, что SortedList это и есть Dictionary, а я сказал - смесь

Qwertiy писал(а):
FireFenix писал(а):Преимущество SortedList над SortedDictionary это наличие Индексов, что позволяет ускорить поиск и не использовать любые виды переборов

Да, обращение по индексду для SortedList O(1), поиск O(lb n).

Зачем отвечать на мои ответы?
Более того, что в теме указан поиск диапазона, так ещё и не учитываешь мой алгоритм, что я привёл с SortedList для выборки диапазона
Птицей Гермеса меня называют, свои крылья пожирая... сам себя я укрощаю
私はヘルメスの鳥 私は自らの羽根を喰らい 飼い慣らされる

FireFenix
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1640
Зарегистрирован: 25.05.2007 (Пт) 10:24
Откуда: Mugen no Sora

Re: Выбрать диапазон ключей

Сообщение FireFenix » 02.04.2013 (Вт) 14:51

kanut писал(а):Это очевидно. За 33 мс мне нужно уже выбрать уйму диапазонов, а не перебрать 1 раз все элементы.

Кстати, 10 млн. записей это максимум, а начинаться коллекция будет с 1 элемента.

А в чём проблема?
Сортированный список диапазонов + 1 проход по массиву = Profit
Птицей Гермеса меня называют, свои крылья пожирая... сам себя я укрощаю
私はヘルメスの鳥 私は自らの羽根を喰らい 飼い慣らされる

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 02.04.2013 (Вт) 14:57

Спасибо всем за помощь, буду делать функцию выборки с SortedList.

Dmitriy2003
Постоялец
Постоялец
 
Сообщения: 690
Зарегистрирован: 27.05.2003 (Вт) 22:47
Откуда: Deutschland

Re: Выбрать диапазон ключей

Сообщение Dmitriy2003 » 02.04.2013 (Вт) 17:15

Не принимая в расчет все вышесказанное - меня результат вполне устраивает, а почему вас нет :?:
Код: Выделить всё
class Program
    {
        static void Main(string[] args)
        {
            int maxVal = 104857600; // 104.857.600
            Dictionary<int, int> srcDict = new Dictionary<int, int>(maxVal);
           
            Stopwatch sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < maxVal; i++) { srcDict.Add(i, i); }

            sw.Stop();
            Console.WriteLine(String.Format("Fill Dictionary (0 to 104.857.600 items): {0} ms.",
                sw.ElapsedMilliseconds));

            sw.Reset();
            sw.Start();

            IEnumerable<KeyValuePair<int, int>> query = srcDict
                .Where<KeyValuePair<int, int>>(item => item.Key > 256789 && item.Key < 1024789)
                .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

            sw.Stop();
            Console.WriteLine(String.Format("Query for > 256.789 and < 1.024.789 : {0} ms, Total Items: {1}",
                sw.ElapsedMilliseconds, query.Count<KeyValuePair<int,int>>()));

            sw.Reset();
            sw.Start();

            query = srcDict
                .Where<KeyValuePair<int, int>>(item => item.Key > 120 && item.Key < 210)
                .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

            sw.Stop();
            Console.WriteLine(String.Format("Query for > 120 and < 210 : {0} ms, Total Items: {1}",
                sw.ElapsedMilliseconds, query.Count<KeyValuePair<int, int>>()));

            sw.Reset();
            sw.Start();

            query = srcDict
                .Where<KeyValuePair<int, int>>(item => item.Key > 104757500 && item.Key < 104857200)
                .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

            sw.Stop();
            Console.WriteLine(String.Format("Query for > 104.757.500 and < 104.857.200 : {0} ms, Total Items: {1}",
                sw.ElapsedMilliseconds, query.Count<KeyValuePair<int, int>>()));

            Console.ReadLine(); 

        }
    }


Код: Выделить всё
class Program
    {
        static void Main(string[] args)
        {
            Dictionary<int, int> base01 = new Dictionary<int, int>(26214400);
            Dictionary<int, int> base02 = new Dictionary<int, int>(26214400);
            Dictionary<int, int> base03 = new Dictionary<int, int>(26214400);
            Dictionary<int, int> base04 = new Dictionary<int, int>(26214400);

            for (int i = 0; i < 26214400; i++) { base01.Add(i, i); }
            for (int i = 26214401; i < 52428800; i++)  { base02.Add(i, i); }
            for (int i = 52428801; i < 78643200; i++)  { base03.Add(i, i); }
            for (int i = 78643201; i < 104857600; i++) { base04.Add(i, i); }

            int maxVal = 104857600; // 104.857.600
            Dictionary<int, int> srcDict = new Dictionary<int, int>(maxVal);

            for (int i = 1; i < 26214401; i++)
            {
                try
                {
                    srcDict.Add(base01[i], base01[i]);
                    srcDict.Add(base04[78643201 + i], base04[78643201 + i]);
                    srcDict.Add(base03[52428801 + i], base03[52428801 + i]);
                    srcDict.Add(base02[26214401 + i], base02[26214401 + i]);
                }
                catch
                {
                    //:-(
                }
            }

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

            IEnumerable<KeyValuePair<int, int>> query1 = srcDict
                .Where<KeyValuePair<int, int>>(item => item.Key > 21214401 && item.Key < 58428801)
                .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

            sw1.Stop();

            Console.WriteLine(String.Format("Query for > 21.214.401 and < 58.428.801: {0} ms, Total Items: {1:000,000,000}",
                sw1.ElapsedMilliseconds, query1.Count<KeyValuePair<int,int>>()));

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

            IEnumerable<KeyValuePair<int, int>> query2 = srcDict
                .Where<KeyValuePair<int, int>>(item => item.Key > 52428701 && item.Key < 59428801)
                .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

            sw2.Stop();
            Console.WriteLine(String.Format("Query for > 52.428.701 and < 59.428.801 : {0} ms, Total Items: {1:000,000,000}",
                sw2.ElapsedMilliseconds, query2.Count<KeyValuePair<int, int>>()));

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

            IEnumerable<KeyValuePair<int, int>> query3 = srcDict
                .Where<KeyValuePair<int, int>>(item => item.Key > 16214401 && item.Key < 29214401)
                .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

            sw3.Stop();
            Console.WriteLine(String.Format("Query for > 16.214.401 and < 29.214.401 : {0} ms, Total Items: {1:000,000,000}",
                sw3.ElapsedMilliseconds, query3.Count<KeyValuePair<int, int>>()));

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

            IEnumerable<KeyValuePair<int, int>> query4 = srcDict
                .Where<KeyValuePair<int, int>>(item => item.Key > 90565 && item.Key < 79428801)
                .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

            sw4.Stop();
            Console.WriteLine(String.Format("Query for > 90.565 and < 79.428.801 : {0} ms, Total Items: {1:000,000,000}",
                sw4.ElapsedMilliseconds, query4.Count<KeyValuePair<int, int>>()));

            Console.ReadLine(); 

        }
    }


Output1 писал(а):Fill Dictionary (0 to 104.857.600 items): 1313 ms.
Query for > 256.789 and < 1.024.789 : 6 ms, Total Items: 767999
Query for > 120 and < 210 : 0 ms, Total Items: 89
Query for > 104.757.500 and < 104.857.200 : 0 ms, Total Items: 99699


Output2 писал(а):Query for > 21.214.401 and < 58.428.801: 6 ms, Total Items: 037 214 395
Query for > 52.428.701 and < 59.428.801 : 0 ms, Total Items: 007 000 097
Query for > 16.214.401 and < 29.214.401 : 0 ms, Total Items: 012 999 997
Query for > 90.565 and < 79.428.801 : 0 ms, Total Items: 079 338 229

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 21:06

kanut писал(а):Да, а я вначале подумал, что это List, просто сортированный

Ну так ты был прав :)

FireFenix писал(а):Опять ты пристал. Человек не говорит зачем ему нужно, а так же возможно он использует массив для хранения индексного дерева некоторых элементов.
С учётом большого количества элементов, выборки диапазонов, сложных условий и удобности лучше использовать СУБД

Я не пристал. Очевидно, что раз требуется высокая производительность, то это вычислительная задача.
И нет ничего что СУБД способна выполнить быстрее, чем код в программе. Если конечно он соответствует задаче.

kanut писал(а):Кстати, 10 млн. записей это максимум, а начинаться коллекция будет с 1 элемента.

Опиши появление новых записей.

FireFenix писал(а):У тебя развитая телепатия и ты знаешь, что для человека быстро?

Да. За O(n) медленно. Быстрее O(lb n) сделать не получится. Чтобы сделать что-то промежуточное между этими вариантами, надо очень сильно извратиться, т. к. все стандартные алгоритмы делают это за O(lb n).

FireFenix писал(а):И что за lb n? Может имелось ввиду log2 n?

Да. Logarithm Binary. Есть у меня привычка так его обозначать.

FireFenix писал(а):И где тут не правда? я же не сказал, что SortedList это и есть Dictionary, а я сказал - смесь

Ты сказал:
FireFenix писал(а):SortedList это смесь List + Dictionary. Имея индексы можно делать поиск хешу и перебирать потом диапазон индексов, но как и SortedDictionary при каждой вставке выполняется сравнение элемента с уже имеющимися в худшем случаю дающее O(log2 n), т.е. если на перебор всего массива требуется 200мс, то для вставки 100мс
По пунктам:
  • SortedList это смесь List + Dictionary. - Неверно. Dictionary использует хэш, SortedDictionary - бинарное дерево, SortedList - массив. Dictionary не отсортирован.
  • Имея индексы можно делать поиск хешу и перебирать потом диапазон индексов - При чём тут хеш? SortedDictionary не использует хэш.
  • как и SortedDictionary при каждой вставке выполняется сравнение элемента с уже имеющимися в худшем случаю дающее O(log2 n) - Неверно. Т. к. для хранения используется список, то сначала выполняется операция поиска за O(lb n), но затем элемент должен быть вставлен в середину массива, что ведёт сдвиг всего хвоста, который даёт O(n), если только не утверждается, что добавление будет происходить в конец.
  • т.е. если на перебор всего массива требуется 200мс, то для вставки 100мс - Вычисления не соответствуют приведённым рассуждениям, однако, результат может быть правдоподобным, хотя и нуждается в дополнительной проверке.

kanut писал(а):Спасибо всем за помощь, буду делать функцию выборки с SortedList.

При этом каждая вставка будет выполняться за O(n). Уверен?

Dmitriy2003 писал(а):Не принимая в расчет все вышесказанное - меня результат вполне устраивает, а почему вас нет :?:

Что-то не так в твоих замерах. И уж точно не стоит использовать Linq там, где важно быстро получить результат.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 21:17

Dmitriy2003 писал(а):
Output1 писал(а):Fill Dictionary (0 to 104.857.600 items): 1313 ms.
Query for > 256.789 and < 1.024.789 : 6 ms, Total Items: 767999
Query for > 120 and < 210 : 0 ms, Total Items: 89
Query for > 104.757.500 and < 104.857.200 : 0 ms, Total Items: 99699

Ты бы хоть по миганию курсора посмотрел интервалы между выводом.
Меняем Stopwatch на DateTime.Now и видим правильное время - около 2 секунд по всем трём пунктам.

Dmitriy2003
Постоялец
Постоялец
 
Сообщения: 690
Зарегистрирован: 27.05.2003 (Вт) 22:47
Откуда: Deutschland

Re: Выбрать диапазон ключей

Сообщение Dmitriy2003 » 02.04.2013 (Вт) 21:18

Qwertiy писал(а):Что-то не так в твоих замерах. И уж точно не стоит использовать Linq там, где важно быстро получить результат.

да там все не так, но как приятно что-та замерить :lol:

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 21:22

Dmitriy2003 писал(а):Не принимая в расчет все вышесказанное - меня результат вполне устраивает, а почему вас нет :?:

Да.. Я понял откуда выплыла разница вго времени. Дело не в StopWatch.

Dmitriy2003 писал(а):
Код: Выделить всё
      sw.Reset();
      sw.Start();
      start = DateTime.Now;

      IEnumerable<KeyValuePair<int, int>> query = srcDict
          .Where<KeyValuePair<int, int>>(item => item.Key > 256789 && item.Key < 1024789)
          .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

      sw.Stop();
      Console.WriteLine(String.Format("Query for > 256.789 and < 1.024.789 : {0} ms {2}, Total Items: {1}",
          sw.ElapsedMilliseconds, query.Count<KeyValuePair<int, int>>(), (DateTime.Now - start).TotalMilliseconds));

Ты понимаешь как это работает?
1. Сбросили таймер.
2. Сохранили текущее время.
3. Сформировали запрос.
4. Остановили таймер.
5. Получили количество прошедших миллисекунд по таймеру.
6. Выполнили запрос на получение элементов и посчитали их количество.
7. Вычислили прошедшее время по текущему времени.

Dmitriy2003
Постоялец
Постоялец
 
Сообщения: 690
Зарегистрирован: 27.05.2003 (Вт) 22:47
Откуда: Deutschland

Re: Выбрать диапазон ключей

Сообщение Dmitriy2003 » 02.04.2013 (Вт) 21:26

Qwertiy писал(а):Ты понимаешь как это работает?

Конечно нет :) , а вот синтаксис задел за живое
Код: Выделить всё
IEnumerable<KeyValuePair<int, int>> query = srcDict
          .Where<KeyValuePair<int, int>>(item => item.Key > 256789 && item.Key < 1024789)
          .Select<KeyValuePair<int, int>, KeyValuePair<int, int>>(item => item);

правда красиво :D

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 02.04.2013 (Вт) 21:36

Dmitriy2003 писал(а):а вот синтаксис задел за живое

Типы у функций компилятор почти всегда определяет сам, поэтому можно короче:
Код: Выделить всё
      IEnumerable<KeyValuePair<int, int>> query = srcDict
          .Where(item => item.Key > 256789 && item.Key < 1024789)
          .Select(item => item);
Кстати, а зачем тут последний select в таком виде? :)

А ещё можно так:
Код: Выделить всё
IEnumerable<KeyValuePair<int, int>> query = from item in srcDict where item.Key > 256789 && item.Key < 1024789 select item;

Да, на VB первый вариант должен выглядеть немного по-другому, без item =>.

Dmitriy2003
Постоялец
Постоялец
 
Сообщения: 690
Зарегистрирован: 27.05.2003 (Вт) 22:47
Откуда: Deutschland

Re: Выбрать диапазон ключей

Сообщение Dmitriy2003 » 02.04.2013 (Вт) 22:27

Qwertiy писал(а):Кстати, а зачем тут последний select в таком виде? :)

Понятия не имею :)
Qwertiy писал(а):А ещё можно так:
Код: Выделить всё
IEnumerable<KeyValuePair<int, int>> query = from item in srcDict where item.Key > 256789 && item.Key < 1024789 select item;

Ну не знаю, конкретно эта строчка не вдохновляет, :D

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 03.04.2013 (Ср) 10:17

Dmitriy2003 писал(а):меня результат вполне устраивает, а почему вас нет


Когда вместо одной выборки будут миллиарды и миллиарды, то разница будет сразу видна.

Qwertiy писал(а): kanut писал(а):Да, а я вначале подумал, что это List, просто сортированный
Ну так ты был прав


Я имел ввиду, что у List нет значений, а есть только ключи.

Qwertiy писал(а):При этом каждая вставка будет выполняться за O(n)


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

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 03.04.2013 (Ср) 11:43

kanut писал(а):Коллекция заполнится только один раз (и при каждой загрузке программы естественно, значениями подряд), а потом будут только выборки диапазонов.

Тогда зачем же ты говорил, что добавление элементов есть?
Тогда, конечно, SortedList. Или даже просто массив. И бинарный поиск.

kanut
Новичок
Новичок
 
Сообщения: 41
Зарегистрирован: 24.03.2013 (Вс) 12:10

Re: Выбрать диапазон ключей

Сообщение kanut » 03.04.2013 (Ср) 13:50

Qwertiy писал(а):Тогда зачем же ты говорил, что добавление элементов есть?
Тогда, конечно, SortedList. Или даже просто массив. И бинарный поиск.


Как зачем? Оно же сначала будет. Добавление неизвестно где расположенного ключа-зачения в отсортированную коллекцию.

Да, если стандартного средства в Framework нет, лучше было бы использовать два массива + свою функцию для выборки. По крайней мере после полного заполнения коллекции. Массивы потом еще в несколько раз увеличат быстродействие.

Интересно, почему в Framework нет никаких готовых решений для моей задачи? Неужели она такая редкая?

След.

Вернуться в Visual Basic .NET

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13

    TopList