Форум программистов, компьютерный форум, киберфорум
Наши страницы

C# для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
Strangers
1 / 1 / 0
Регистрация: 08.02.2013
Сообщений: 47
#1

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

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

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

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

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

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

Уникальные элементы матрицы - C#
Дана матрица найти уникальные элементы матрицы и их количество. Уникальным считается если от этого элемента справа стоят все элементы...

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

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

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

33
агерон
271 / 272 / 33
Регистрация: 12.10.2009
Сообщений: 1,077
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 / 29
Регистрация: 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
6191 / 3394 / 1032
Регистрация: 11.02.2013
Сообщений: 7,489
Завершенные тесты: 3
11.12.2013, 01:22 #5
Цитата Сообщение от Strangers Посмотреть сообщение
LINQ мне не подходит.
Цитата Сообщение от Strangers Посмотреть сообщение
Перебирать циклами очень долго получается
Вы, батенька, эстет. Так что же вы хотите?
0
агерон
271 / 272 / 33
Регистрация: 12.10.2009
Сообщений: 1,077
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
агерон
271 / 272 / 33
Регистрация: 12.10.2009
Сообщений: 1,077
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
агерон
271 / 272 / 33
Регистрация: 12.10.2009
Сообщений: 1,077
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
151 / 181 / 18
Регистрация: 25.11.2013
Сообщений: 978
11.12.2013, 10:24 #11
А если бы IPAddress парсить самому, а не с помощью Regex и прочего, тогда бы и чтение раза в 3 быстрее было.
Справедливости ради следует сказать, что для измерения используют класс Stopwatch
0
агерон
271 / 272 / 33
Регистрация: 12.10.2009
Сообщений: 1,077
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
агерон
271 / 272 / 33
Регистрация: 12.10.2009
Сообщений: 1,077
11.12.2013, 11:36 #14
кхм... сложно однако....
тогда я тебе советую 1 раз выбрать все ip из лога в List<uint> и сереализовать его ip.bin а потом уже другой частью программы подгружать этот ip.bin и обрабатывать
P. S. если не секрет откуда такие логи?
0
DataPlanner
151 / 181 / 18
Регистрация: 25.11.2013
Сообщений: 978
11.12.2013, 11:58 #15
Цитата Сообщение от агерон Посмотреть сообщение
вы знаете сколько памяти занимает 15000000 обьектов IPAddress? если нет то я вас просвещу 1,04 Гб
1. IP адрес это 16 байт (точнее 15), умножить на 15 млн полагаю вы и сами сможете.
2. Прочитайте файл в 15 млн, думаю, уложитесь в пару секунд, в зависимости от скорости HDD
0
11.12.2013, 11:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 11:58
Привет! Вот еще темы с ответами:

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

В списке все элементы различны. Поменяйте местами минимальный и максимальный элемент этого списка - C#
В списке все элементы различны. Поменяйте местами минимальный и максимальный элемент этого списка. входные данные 3 4 5 2 1 ...

Поиск слова в большом тексте - C#
Здравствуйте, у меня есть большой текст, необходимо в нем найти слово введенное в textBox. Проблема в том, что в небольших текстах, все...

Подсчет строк в большом файле - C#
Здравствуйте, каким образом можно подсчитать количество строк в файлах допустим 4 gb 5 gb 10 gb 100 gb. Насколько знаю максимальная...


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

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

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