Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
Strangers
1 / 1 / 0
Регистрация: 08.02.2013
Сообщений: 47
1

Уникальные элементы в большом списке

10.12.2013, 23:52. Просмотров 2443. Ответов 33
Метки нет (Все метки)

Задача состоит в следующем: есть List<string> в котором 15 миллионов записей. Мне нужно подсчитать сколько раз встречается каждый уникальный элемент и вывести элементы в порядке наибольшего количество повторений до наименьшего.

Делал через LINQ, но с небольшими списками. После того как количество элементов перевалило за 2 миллиона LINQ не тянет. Перебирать циклами очень долго получается. Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2013, 23:52
Ответы с готовыми решениями:

Найти в массиве повторяющиеся элементы и записать только уникальные элементы в новый массив из первого массива
Всем привет. Можете помочь написать такой алгоритм, нужно в одном массиве...

Уникальные элементы матрицы
Дана матрица найти уникальные элементы матрицы и их количество. Уникальным...

Уникальные элементы списка
Есть два List&lt;string&gt;. Каким образом найти все элементы первого списка, которых...

Поменять положительные элементы в списке
Здравствуйте, мне нужно поменять положительные элементы в списке на число &quot;R&quot;,...

Как найти одинаковые элементы в списке List
Нужно найти все не уникальные числа последовательности, метод Distinct не...

33
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 00:44 2
вот тебе код только не плачь
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
using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Diagnostics;
using System.Linq;
 
namespace _1036672
{
    class Program
    {
        static void Main(string[] args)
        {
            var timer = new Stopwatch();
            timer.Start();
            var data = GenerationData(15000000);
            timer.Stop();
            timer.Start();
            data.Cast<string>()
                .GroupBy(x => x)
                .OrderBy(x => x.LongCount())
                .ToList()
                .ForEach(x => Console.WriteLine("Key: {0}, Count: {1}", x.Key, x.LongCount()));
            timer.Stop();
            Console.ReadLine();
        }
 
        public static StringCollection GenerationData(int count)
        {
            var random = new Random();
            var result = new StringCollection();
            for (var i = 0; i < count; i++)
                result.Add(Convert.ToString(random.Next(0, 1000)));
            return result;
        }
    }
}
как ты и просил 15000000 элементов
кстати понятие "долго" это растяжимо вот у меня генерация элементов занимает 3,81 секунды + 5,34 секунды остальные подсчеты с выводом на экран, и для данного количества элементов это не долго
0
Anderok
110 / 110 / 70
Регистрация: 10.11.2013
Сообщений: 446
11.12.2013, 01:02 3
агерон, линки придумали для домохозяек, чтобы они могли себе сайты наскоро писать. Они мееееедленные!
0
Strangers
1 / 1 / 0
Регистрация: 08.02.2013
Сообщений: 47
11.12.2013, 01:08  [ТС] 4
Спасибо, но как я сказал LINQ мне не подходит.
0
ViterAlex
6462 / 3632 / 1484
Регистрация: 11.02.2013
Сообщений: 7,990
Завершенные тесты: 3
11.12.2013, 01:22 5
Цитата Сообщение от Strangers Посмотреть сообщение
LINQ мне не подходит.
Цитата Сообщение от Strangers Посмотреть сообщение
Перебирать циклами очень долго получается
Вы, батенька, эстет. Так что же вы хотите?
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 01:31 6
медленно? давайте ка посчитаем 5,34 секунды уходит на обработку 15000000 элементов что равно 0,000000356 сек или 3 тика таймера на обработку 1 элемента вы считаете что это долго? и чем это вам Linq не подходит? религия не позволяет использовать? или вы думаете что вам 15000000 элементов обработают за один тик таймера?
0
Strangers
1 / 1 / 0
Регистрация: 08.02.2013
Сообщений: 47
11.12.2013, 01:38  [ТС] 7
Цитата Сообщение от ViterAlex Посмотреть сообщение
Вы, батенька, эстет. Так что же вы хотите?
Дело не в том что эстет. Я очень люблю LINQ,но он почему то не отрабатывает в данном случае. А циклы работаю непозволительно долго. Возможно есть третий вариант?

Добавлено через 31 секунду
Цитата Сообщение от агерон Посмотреть сообщение
медленно? давайте ка посчитаем 5,34 секунды уходит на обработку 15000000 элементов что равно 0,000000356 сек или 3 тика таймера на обработку 1 элемента вы считаете что это долго? и чем это вам Linq не подходит? религия не позволяет использовать? или вы думаете что вам 15000000 элементов обработают за один тик таймера?
В моем случае LINQ не отрабатывает запрос почему то...
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 01:41 8
кхм.. а может вы таки предоставите на суд общественности исходный код своего проекта?

Добавлено через 40 секунд
т. к. мой код отрабатывает корректно и в данных условиях довольно шустро
0
Strangers
1 / 1 / 0
Регистрация: 08.02.2013
Сообщений: 47
11.12.2013, 03:17  [ТС] 9
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
           string regExPattern = @"\b([01]?\d\d?|2[0-4]\d|25[0-5])\." +
                                  @"([01]?\d\d?|2[0-4]\d|25[0-5])\." +
                                  @"([01]?\d\d?|2[0-4]\d|25[0-5])\." +
                                  @"([01]?\d\d?|2[0-4]\d|25[0-5])\b";
 
            Regex ip_RegEx = new Regex(regExPattern);
            MatchCollection result;
            List<string> ip_addresses = new List<string>();
            ipList = new List<IP_Info>();
 
            System.IO.StreamReader file = new System.IO.StreamReader(logFileName);
            string line;
 
            while ((line = file.ReadLine()) != null)
            {
                result = ip_RegEx.Matches(line);
                if (result.Count != 0)
                {
                    ip_addresses.Add(result[0].Value);
                }
            }
            file.Close();
            
 
            var query = from ip in ip_addresses
                        group ip by ip into groups
                        let count = groups.Count()
                        orderby count descending
                        select new { ip = groups.Key, count = count };
Вот код, до LINQ все корректно работает. После - не работает.
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 06:02 10
свой код можете выкинуть на помойку, среднее потребление памяти вашим алгоритмом примерно 740 мегабайт, он отрабатывает в среднем за 32 сек при чем 30 из них уходит на предварительную подготовку данных, чтение с диска, а 2 на работу linq запроса
вот вам оптимизированный по памяти код, он на хранение 15000000 ip адресов использует чуть больше 60 мегабайт, время вычитки правда чуть дольше чем у вас 37 сек
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;
using System.Text.RegularExpressions;
 
namespace _1036672
{
    class Program
    {
        static void Main(string[] args)
        {
            long start, end;
            start = DateTime.Now.Ticks;
            GenerateData(15000000);
            end = DateTime.Now.Ticks;
            Console.Write("Time of data generation: {0} sec", new TimeSpan(end - start));
            Console.ReadLine();
            IEnumerable<uint> data;
            start = DateTime.Now.Ticks;
            using (var readFile = File.OpenRead("ip.txt"))
            using (var bufferedStream = new BufferedStream(readFile, 1048576))
            using (var reader = new StreamReader(bufferedStream))
                data = GetIPAddress(reader).ToList();
            end = DateTime.Now.Ticks;
            Console.Write("Data is being read: {0} sec", new TimeSpan(end - start));
            Console.ReadLine();
            start = DateTime.Now.Ticks;
            data.GroupBy(element => element)
                .OrderBy(element => element.LongCount())
                .Reverse()
                .ToList()
                .ForEach(element => Console.WriteLine("Ip: {0}, Count: {1}", new IPAddress(element.Key), element.Count()));
            end = DateTime.Now.Ticks;
            Console.WriteLine("Time data: {0} sec", new TimeSpan(end - start));
            Console.ReadLine();
        }
 
        public static IEnumerable<uint> GetIPAddress(StreamReader reader)
        {
            const string pattern = "(?<address>(\\d{1,3}\\.{0,1}){4})";
            const string address = "address";
            while (!reader.EndOfStream)
            {
                var data = reader.ReadLine();
                var ipString =
                    Regex.Match(data, pattern, RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Singleline)
                         .Groups[address].Value;
                var ipBytes = IPAddress.Parse(ipString).GetAddressBytes();
                yield return BitConverter.ToUInt32(ipBytes, 0);
            }
        }
 
        public static void GenerateData(int count)
        {
            var random = new Random();
            using (var writeFile = File.OpenWrite("ip.txt"))
            using (var bufferedStream = new BufferedStream(writeFile, 1048576))
            using (var writer = new StreamWriter(bufferedStream))
            {
                for (int i = 0; i < count; i++)
                {
                    if (i<count-1)
                        writer.WriteLine("10.1.{0}.{1}", random.Next(0, 3), random.Next(1, 254));
                    else
                        writer.Write("10.1.{0}.{1}", random.Next(0, 3), random.Next(1, 254));
                }
            }
        }
    }
}
P. S. в заключение могу сказать только то что вы искали проблему не в том месте, что в моем, что в вашем случае Linq запрос отрабатывает за 1-3 сек а вот первичная подготовка данных занимает 30-40 сек что фактически являет собой 95% времени работы программы
0
DataPlanner
153 / 183 / 49
Регистрация: 25.11.2013
Сообщений: 978
11.12.2013, 10:24 11
А если бы IPAddress парсить самому, а не с помощью Regex и прочего, тогда бы и чтение раза в 3 быстрее было.
Справедливости ради следует сказать, что для измерения используют класс Stopwatch
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 10:54 12
DataPlanner, вы так уверены? вы знаете сколько памяти занимает 15000000 обьектов IPAddress? если нет то я вас просвещу 1,04 Гб ну это так к сведению а на счет чтения я вас тоже должен разочаровать, текстовой файл в котором содержится только одни ipv4 адреса в 15000000 штук занимает 168 метров а если там какой либо лог который может достигать пару гигов обьемом?
0
Strangers
1 / 1 / 0
Регистрация: 08.02.2013
Сообщений: 47
11.12.2013, 11:23  [ТС] 13
Собственно говоря у меня лог файл 23ГБ.
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 11:36 14
кхм... сложно однако....
тогда я тебе советую 1 раз выбрать все ip из лога в List<uint> и сереализовать его ip.bin а потом уже другой частью программы подгружать этот ip.bin и обрабатывать
P. S. если не секрет откуда такие логи?
0
DataPlanner
153 / 183 / 49
Регистрация: 25.11.2013
Сообщений: 978
11.12.2013, 11:58 15
Цитата Сообщение от агерон Посмотреть сообщение
вы знаете сколько памяти занимает 15000000 обьектов IPAddress? если нет то я вас просвещу 1,04 Гб
1. IP адрес это 16 байт (точнее 15), умножить на 15 млн полагаю вы и сами сможете.
2. Прочитайте файл в 15 млн, думаю, уложитесь в пару секунд, в зависимости от скорости HDD
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 12:38 16
вы так уверены? смотря какой ip, вы уверены что при чтении и разборе 15000000 строковых представлений ipv4 в List<IPAddress> который также будет содержать 15000000 обьектов IpAddress вы займете всего 60 метров? хорошо давайте посчитаем
1) 1 строковое представление адреса ipv4 - 15 байт
2) обьем обьекта типа IPAddress - 72 байта
а теперь будем считать в самой грубой прикидке 15*15000000 = 225000000б - 219726 кб - 214мб - это обьем 15000000 ipv4 в txt файле а как нам известно у ТС логи в 23Гб
а теперь будем считать обьем List<IPAddress> когда в нем 15000000 элементов 15000000*72 = 1080000000б - 1054687 кб - 1029 мб - 1,0058Гб не верите расчетам проверьте в живую в программе
Дорогой мой поверь мне я уже 14 лет занимаюсь программированием так что не надо мне ляля, список List<uint> это самое оптимальное в данном случае хранилище данных, и мне пофигу что подготовка данных идет 37 секунд сделав парсинг логов 1 раз и подождав пускай даже час в будущем я не буду иметь проблем с обработкой данного массива информации. DataPlanner лучше пойди почитай книжки по программированию, чем писать маразм насчет мгновенного парсинга логов
0
Strangers
1 / 1 / 0
Регистрация: 08.02.2013
Сообщений: 47
11.12.2013, 12:43  [ТС] 17
Цитата Сообщение от агерон Посмотреть сообщение
кхм... сложно однако....
тогда я тебе советую 1 раз выбрать все ip из лога в List<uint> и сереализовать его ip.bin а потом уже другой частью программы подгружать этот ip.bin и обрабатывать
P. S. если не секрет откуда такие логи?
С Веб-сервера после DDoS-а. Спасибо, Ваш код отлично отработал.
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 12:47 18
Strangers, пожалуйста если нужно то обращайся
0
DataPlanner
153 / 183 / 49
Регистрация: 25.11.2013
Сообщений: 978
11.12.2013, 12:53 19
Цитата Сообщение от агерон Посмотреть сообщение
поверь мне я уже 14 лет занимаюсь программированием
1. Я верю только в аргументы, таковых пока не обнаружил.
2. Если парсить вот так: IPAddress.Parse(ipString).GetAddressBytes(); не удивляюсь, что это занимает 37 секунд
3. И кстати, откуда такая приверженность к uint в контексте данного кода, int уже не справляется?
0
агерон
274 / 281 / 58
Регистрация: 12.10.2009
Сообщений: 1,108
11.12.2013, 13:19 20
Data planner брысь учиться, ты нифига не понимаешь в программировании
1) загрузить текстовой файл даже в 2Гб как единый кусок в память нужно прежде всего иметь свободную память доступного обьема, а так как у TC файл в 23 ГБ... ну ты понял, разве что у тебя есть хотя бы 32-40гб памяти на борту материнки
2) раз мы не можем прочитать файл сразу то нам нужно его читать построчно, можно конечно и не построчно а по-блочно но это лишний геморой который ни мне ни TC не нужен, правда если ты читал мой код в теме то ты должен заметить вот эти строки
C#
1
2
3
            using (var readFile = File.OpenRead("ip.txt"))
            using (var bufferedStream = new BufferedStream(readFile, 1048576))
            using (var reader = new StreamReader(bufferedStream))
которые по сути являются буферизацией чтения файла с диска
дальше у тебя есть альтернатива IPAddress.Parse(ipString).GetAddressBytes()? предлагай замеры времени не сложно сделать т. к. ты совсем не понимаешь что проблема не в этой строчке а в том что я построчно читаю файл, которая истекает из текущего обьема логов TC
3) мне пофигу что ты мне неверишь на счет опыта, еще раз повторяю брысь книжки читать по программированию, как минимум потому что кроме голословных утверждений от тебя не видно НИЧЕГО , ни единой строчки кода а тем паче ни единого варианта решения задачи

Добавлено через 9 минут
P. S. если ты не знаешь то я тебя просвещу что int что uint все одинаково по объему выделяемой памяти под элемент (4 байта) различие только в трактовке старшего бита как показателя знака, а в данном случае uint облегчает понимание т. к. не бывает отрицательных сетевых адресов
0
11.12.2013, 13:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 13:19

В списке все элементы, стоящие перед максимальным, заменить на 0
Помогите, пожалуйста, с этой прогой. (То, что должна выполнять прога: Ввод...

Новый список, содержащий элементы списка A, отсутствующие в списке B
Даны два объекта A, B типа List&lt;int&gt; Нужно создать новый список, который...

Массив целых чисел «свернуть в кольцо» и упорядочить элементы в списке по возрастанию
Помогите, дали задание написать программу в виндовс форм, ни разу не работал в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru