Как лучше работать с несколькими миллионами строк

[медведко]

Здравствуйте!

Простите, если вопрос совсем глупый. Но если не трудно, направьте в нужную сторону, пожалуйста.

Итак, стоит передо мной задача (вообще, я админ) проанализировать журнал(лог) прокси сервера. При этом агрегировать похожие записи.
Т.е. допустим, в течение дня Вася ходил на Яндекс 20 раз, на Гугл - 10, на третий сайт 15 итд. Мы в итоговый массив данных будем не каждую новую строчку заносить, а добавлять к уже существующей объем скачанного.

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

Я делал многомерный массив, 5 (пользователь, сайт, байтысюда, байтытуда, времяобработки ) на 3.000.000 элементов.

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

Работает это всё нестабильно. Если количество уникальных пар пользователь+сайт меньше 500 тысяч, всё летает. Но когда их становится миллион или 2.5млн, то обрабатывается всё по 8-10 часов. А это слишком медленно.

Пробовал оптимизировать, но результат всё-равно не устраивает.
Сначала перебор записей делал по циклу for от начала до конца, когда
нашли запись, break. Потом поменял на Array.Indexof (для этого пришлось завести 4 массива, в одном одной строкой пользователь+сайт - по нему и ищет Array.Indexof, в остальных байты и время. Стало быстрее раз в 10, но всё-равно по нескольку часов думает.

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

Посоветуйте, пожалуйста, что ещё попробовать?
Чтобы был быстрый поиск строки в массиве, но при этом и возможности менять строки. То есть stringbuilder не подходит (вроде).

Dataset тоже умрет на таких объемах, по-моему, если сначала загрузить все несколько миллионов записей, а потом пытаться агрегировать. А если каждый раз select дергать, то, подозреваю, что тоже всё очень медленно будет.

[pu4koff]

Dictionary по ключу будет искать быстрее, чем Array.Indexof.
Для таких объемов не грех и СУБД простенькую какую-нибудь прикрутить

[Utkin]

Раздели массив на массивы. Создай на каждую букву фамилии/ника юзеров свой массив. Если Ивановых будет все равно больше 500 000 разбей на несколько и их.

[m0nax]

можно использовать например SortedList (быстрый двоичный поиск)
ключом будет вася(или даже его хеш), а значением еще один словарь сайт-количество

если я правильно понял то типа такого

   
//словарь вася-сайты        
 SortedList<string, SortedList<string, int>> fooo = new ...;
           
//вытаскиваем словарь сайтов и их посещений
            SortedList<string, int> sites;  
            if (fooo.TryGetValue("вася иванов", out sites))
            {
                sites["yandex"]++;//тут тоже надо TryGetValue на случай если яндекса еще нет
            }

можно в принципе вместо внутреннего словаря и двумерный массив сделать, там наверно не так уж много сайтов

[медведко]

Большое спасибо! Как засунуть класс в словарь не осилил (точнее, как потом с ним работать), но даже переход на словарь из двух строк дал дикий прирост скорости - теперь даже самые большие файлы обрабатываются за несколько секунд.

Благодарю!