Сравнение 2 огромных списков с использованием C # несколько раз (с изюминкой)
https://stackoverflow.com/questions/1046278
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Всем привет, у вас здесь отличное сообщество.Я инженер-электрик, занимаюсь кое-какой работой по "программированию" на стороне, чтобы помочь оплачивать счета.Я говорю это, потому что хочу, чтобы вы приняли во внимание, что у меня нет надлежащей подготовки в области компьютерных наук, но я занимаюсь программированием последние 7 лет.
У меня есть несколько таблиц Excel с информацией (все числовые), в основном это "набранные телефонные номера" в одном столбце и количество минут до каждого из этих номеров в другом.Отдельно у меня есть список "номеров префиксных кодов перевозчика" для разных перевозчиков в моей стране.Что я хочу сделать, так это разделить весь "трафик" для каждого оператора.Вот такой сценарий:
Строка первого набранного номера: 123456789ABCD,100 <-- Это будет 13-значный номер телефона и 100 минут.
У меня есть список из более чем 12 000 префиксных кодов для carrier 1, эти коды различаются по длине, и мне нужно проверить каждый из них:
Префиксный код 1: 1234567 <-- этот код состоит из 7 цифр.
Мне нужно проверить первые 7 цифр набранного номера и сравнить его с набранным номером, если совпадение найдено, я бы добавил количество минут к промежуточному итогу для последующего использования. Пожалуйста, учтите, что не все префиксные коды имеют одинаковую длину, иногда они короче или длиннее.
Большая часть этого должна быть проще простого, и я мог бы, должен был бы это сделать, но меня немного пугает огромный объем данных;Иногда списки набранных номеров содержат до 30 000 номеров, а "код префикса оператора" содержит около 13 000 строк, и я обычно проверяю 3 оператора, это означает, что мне приходится делать много "совпадений".
У кого-нибудь есть идея о том, как сделать это эффективно, используя C #?Или на любом другом языке, если быть по-доброму честным.Мне нужно делать это довольно часто, и разработка инструмента для этого имела бы гораздо больше смысла.Мне нужна хорошая точка зрения от кого-то, у кого действительно есть опыт работы в области "Информатики".
Списки не обязательно должны быть в таблицах Excel, я могу экспортировать в CSV-файл и работать оттуда, мне не нужен интерфейс "MS Office".
Спасибо за вашу помощь.
Обновить:
Спасибо вам всем, что уделили время ответу на мой вопрос.Я предполагаю, что в своем невежестве я чрезмерно преувеличил слово "эффективный".Я не выполняю эту задачу каждые несколько секунд.Это то, что я должен делать один раз в день, и я ненавижу делать с Excel, VLOOKUPs и т.д.
Я узнал о новых концепциях от вас, ребята, и я надеюсь, что смогу создать решение (ы), используя ваши идеи.
Решение
Обновить
Вы можете выполнить простой трюк - сгруппировать префиксы по их первым цифрам в словаре и сопоставлять цифры только с правильным подмножеством.Я протестировал это со следующими двумя операторами LINQ, предполагая, что каждый префикс имеет по крайней мере три digis.
const Int32 minimumPrefixLength = 3;
var groupedPefixes = prefixes
.GroupBy(p => p.Substring(0, minimumPrefixLength))
.ToDictionary(g => g.Key, g => g);
var numberPrefixes = numbers
.Select(n => groupedPefixes[n.Substring(0, minimumPrefixLength)]
.First(n.StartsWith))
.ToList();
Итак, насколько это быстро? 15 000 префиксов и 50.000 чисел заняли менее 250 миллисекунд. Достаточно быстро для двух строк кода?
Обратите внимание, что производительность сильно зависит от минимальной длины префикса (MPL), следовательно, от количества групп префиксов, которые вы можете создать.
MPL Runtime
-----------------
1 10.198 ms
2 1.179 ms
3 205 ms
4 130 ms
5 107 ms
Просто чтобы дать приблизительное представление - я провел всего одну пробежку, а впереди еще много чего происходит.
Оригинальный ответ
Я бы не особо заботился о производительности - средний настольный ПК может спокойно работать с таблицами базы данных со 100 миллионами строк.Может быть, это займет пять минут, но я предполагаю, что вы не хотите выполнять задачу через секунду.
Я только что сделал тест.Я сгенерировал список из 15 000 уникальных префиксов длиной от 5 до 10 цифр.Из этих префиксов я сгенерировал 50.000 чисел с префиксом и дополнительными 5-10 цифрами.
List<String> prefixes = GeneratePrefixes();
List<String> numbers = GenerateNumbers(prefixes);
Затем я использовал следующий запрос LINQ to Object, чтобы найти префикс каждого числа.
var numberPrefixes = numbers.Select(n => prefixes.First(n.StartsWith)).ToList();
Ну, на моем ноутбуке Core 2 Duo с частотой 2,0 ГГц это заняло около минуты.Так что, если время обработки в одну минуту приемлемо, может быть, в две или три, если вы включите агрегацию, я бы не пытался что-либо оптимизировать.Конечно, было бы действительно неплохо, если бы программа могла выполнить задачу за секунду или две, но это добавит совсем немного сложности и многое можно будет сделать неправильно.А на проектирование, написание и тестирование требуется время.Выполнение инструкции LINQ заняло у меня всего несколько секунд.
Тестовое приложение
Обратите внимание, что генерация большого количества префиксов происходит очень медленно и может занять минуту или две.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
namespace Test
{
static class Program
{
static void Main()
{
// Set number of prefixes and calls to not more than 50 to get results
// printed to the console.
Console.Write("Generating prefixes");
List<String> prefixes = Program.GeneratePrefixes(5, 10, 15);
Console.WriteLine();
Console.Write("Generating calls");
List<Call> calls = Program.GenerateCalls(prefixes, 5, 10, 50);
Console.WriteLine();
Console.WriteLine("Processing started.");
Stopwatch stopwatch = new Stopwatch();
const Int32 minimumPrefixLength = 5;
stopwatch.Start();
var groupedPefixes = prefixes
.GroupBy(p => p.Substring(0, minimumPrefixLength))
.ToDictionary(g => g.Key, g => g);
var result = calls
.GroupBy(c => groupedPefixes[c.Number.Substring(0, minimumPrefixLength)]
.First(c.Number.StartsWith))
.Select(g => new Call(g.Key, g.Sum(i => i.Duration)))
.ToList();
stopwatch.Stop();
Console.WriteLine("Processing finished.");
Console.WriteLine(stopwatch.Elapsed);
if ((prefixes.Count <= 50) && (calls.Count <= 50))
{
Console.WriteLine("Prefixes");
foreach (String prefix in prefixes.OrderBy(p => p))
{
Console.WriteLine(String.Format(" prefix={0}", prefix));
}
Console.WriteLine("Calls");
foreach (Call call in calls.OrderBy(c => c.Number).ThenBy(c => c.Duration))
{
Console.WriteLine(String.Format(" number={0} duration={1}", call.Number, call.Duration));
}
Console.WriteLine("Result");
foreach (Call call in result.OrderBy(c => c.Number))
{
Console.WriteLine(String.Format(" prefix={0} accumulated duration={1}", call.Number, call.Duration));
}
}
Console.ReadLine();
}
private static List<String> GeneratePrefixes(Int32 minimumLength, Int32 maximumLength, Int32 count)
{
Random random = new Random();
List<String> prefixes = new List<String>(count);
StringBuilder stringBuilder = new StringBuilder(maximumLength);
while (prefixes.Count < count)
{
stringBuilder.Length = 0;
for (int i = 0; i < random.Next(minimumLength, maximumLength + 1); i++)
{
stringBuilder.Append(random.Next(10));
}
String prefix = stringBuilder.ToString();
if (prefixes.Count % 1000 == 0)
{
Console.Write(".");
}
if (prefixes.All(p => !p.StartsWith(prefix) && !prefix.StartsWith(p)))
{
prefixes.Add(stringBuilder.ToString());
}
}
return prefixes;
}
private static List<Call> GenerateCalls(List<String> prefixes, Int32 minimumLength, Int32 maximumLength, Int32 count)
{
Random random = new Random();
List<Call> calls = new List<Call>(count);
StringBuilder stringBuilder = new StringBuilder();
while (calls.Count < count)
{
stringBuilder.Length = 0;
stringBuilder.Append(prefixes[random.Next(prefixes.Count)]);
for (int i = 0; i < random.Next(minimumLength, maximumLength + 1); i++)
{
stringBuilder.Append(random.Next(10));
}
if (calls.Count % 1000 == 0)
{
Console.Write(".");
}
calls.Add(new Call(stringBuilder.ToString(), random.Next(1000)));
}
return calls;
}
private class Call
{
public Call (String number, Decimal duration)
{
this.Number = number;
this.Duration = duration;
}
public String Number { get; private set; }
public Decimal Duration { get; private set; }
}
}
}
Другие советы
Мне кажется, что вам нужно построить три из префиксов-носителей.В итоге вы получите единственное дерево, где конечные узлы сообщают вам несущую для этого префикса.
Затем создайте словарь из носителя в int или long (общая сумма).
Затем для каждой строки набранного номера просто продвигайтесь вниз по списку, пока не найдете оператора связи.Найдите общее количество минут, затраченных на данный момент перевозчиком, и добавьте текущую строку - затем двигайтесь дальше.
Самой простой структурой данных, которая делала бы это достаточно эффективно, был бы список наборов.Создайте набор для каждого носителя, содержащий все префиксы.
Теперь, чтобы связать вызов с оператором:
foreach (Carrier carrier in carriers)
{
bool found = false;
for (int length = 1; length <= 7; length++)
{
int prefix = ExtractDigits(callNumber, length);
if (carrier.Prefixes.Contains(prefix))
{
carrier.Calls.Add(callNumber);
found = true;
break;
}
}
if (found)
break;
}
Если у вас 10 операторов, в наборе будет 70 запросов на каждый звонок.Но поиск в наборе происходит не слишком медленно (намного быстрее, чем линейный поиск).Таким образом, это должно дать вам довольно большую скорость по сравнению с линейным поиском методом перебора.
Вы можете пойти еще дальше и сгруппировать префиксы для каждого носителя в соответствии с длиной.Таким образом, если у носителя есть только префиксы длиной 7 и 4, вы бы знали, что нужно только извлекать и искать эти длины, каждый раз просматривая набор префиксов этой длины.
Как насчет того, чтобы поместить ваши данные в пару таблиц базы данных, а затем запросить их с помощью SQL?Полегче!
CREATE TABLE dbo.dialled_numbers ( number VARCHAR(100), minutes INT )
CREATE TABLE dbo.prefixes ( prefix VARCHAR(100) )
-- now populate the tables, create indexes etc
-- and then just run your query...
SELECT p.prefix,
SUM(n.minutes) AS total_minutes
FROM dbo.dialled_numbers AS n
INNER JOIN dbo.prefixes AS p
ON n.number LIKE p.prefix + '%'
GROUP BY p.prefix
(Это было написано для SQL Server, но должно быть очень просто перевести для любой другой СУБД.)
Возможно, было бы проще (не обязательно эффективнее) сделать это в базе данных вместо C #.
Вы могли бы вставить строки в базу данных и при вставке определить носитель и включить его в запись (возможно, в триггер вставки).
Тогда ваш отчет представлял бы собой запрос суммы в таблице.
Вероятно, я бы просто поместил записи в список, отсортировал его, а затем использовал бинарный поиск искать совпадения.Настройте критерии соответствия двоичного поиска так, чтобы возвращался первый соответствующий элемент, затем выполняйте итерацию по списку, пока не найдете тот, который не соответствует.Бинарный поиск занимает всего около 15 сравнений для поиска по списку из 30 000 элементов.
Возможно, вы захотите использовать Хэш - таблица в C#.
Таким образом, у вас есть пары ключ-значение, и вашими ключами могут быть номера телефонов, а вашим значением - общее количество минут.Если в наборе ключей найдено совпадение, измените общее количество минут, в противном случае добавьте новый ключ.
Затем вам просто нужно будет изменить свой алгоритм поиска, чтобы смотреть не на весь ключ, а только на первые 7 его цифр.
