Comparando 2 enormes listas usando C # várias vezes (com um toque)
https://stackoverflow.com/questions/1046278
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Olá a todos, grande comunidade que tem aqui. Eu sou um engenheiro electrotécnico fazendo algum trabalho "programação" do lado para ajudar a pagar as contas. Digo isso porque eu quero que você levar em consideração que eu não tenho formação adequada Ciência da Computação, mas tenho vindo a codificação durante os últimos 7 anos.
Eu tenho várias tabelas do Excel com informação (todo numérico), "números de telefone discados" Basicamente é em uma coluna e número de minutos para cada um desses números no outro. Separadamente Eu tenho uma lista de "números de código de prefixo transportadora" para as operadoras diferentes no meu país. O que eu quero fazer é separar todo o "tráfego" por transportadora. Aqui está o cenário:
número da linha Primeira marcado : 123456789ABCD, 100 <- Isso seria um número de telefone de 13 dígitos e 100 minutos.
Eu tenho uma lista de 12.000+ códigos de prefixo para suporte 1, estes códigos variam em tamanho, e eu preciso verificar cada um deles:
Código 1 Prefixo : 1234567 <- este código é de 7 dígitos.
Eu preciso verificar os primeiros 7 dígitos para o número discado um compará-lo com o número discado, se for encontrada uma correspondência, gostaria de acrescentar o número de minutos para um subtotal para uso posterior. Por favor, considere que nem todos os códigos de prefixo são do mesmo comprimento, algumas vezes eles são mais curtos ou mais.
A maior parte deste deve ser um pedaço de bolo, e eu podia deve ser capaz de fazê-lo, mas eu estou ficando um pouco assustado com a enorme quantidade de dados; Algumas vezes as listas de números discados consiste de até 30.000 números e os "portador de código prefixo" listas cerca de 13.000 linhas longas, e eu costumo verificar 3 transportadores, isso significa que eu tenho que fazer um monte de "partidas".
Alguém tem uma idéia de como fazer isso de forma eficiente usando C #? Ou qualquer outra linguagem para ser gentil honesto. Eu preciso fazer isso com bastante frequência e projetar uma ferramenta para fazer isso faria muito mais sentido. Eu preciso de uma boa perspectiva de alguém que tem esse fundo "Cientista Computador".
As listas não precisa estar em planilhas do Excel, posso exportar para arquivo CSV e trabalhar a partir daí, eu não preciso de uma interface "MS Office".
Obrigado por sua ajuda.
Update:
Obrigado a todos por seu tempo em responder a minha pergunta. Eu acho que na minha ignorância eu mais exagerada a palavra "eficiente". Eu não executar esta tarefa a cada poucos segundos. É algo que eu tenho que fazer uma vez por dia e eu odeio a ver com com Excel e VLOOKUPs, etc.
eu aprendi sobre novos conceitos de vocês e eu espero que eu possa construir uma solução (s) usando suas idéias.
Solução
Atualizar
Você pode fazer um truque simples - grupo os prefixos por seus primeiros dígitos em um dicionário e combinar os números apenas contra o subconjunto correta. Eu testei-o com as duas seguintes declarações LINQ assumindo cada prefixo tem pelo menos três 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();
Então, o quão rápido é isso? 15.000 prefixos e 50.000 números levou menos de 250 milissegundos. rápido o suficiente para duas linhas de código?
Note-se que o desempenho depende fortemente do comprimento prefixo mínimo (MPL), por conseguinte, sobre o número de grupos de prefixo pode construir.
MPL Runtime
-----------------
1 10.198 ms
2 1.179 ms
3 205 ms
4 130 ms
5 107 ms
Só para dar uma idéia aproximada -. Fiz apenas uma corrida e tem um monte de outras coisas acontecendo
resposta Original
Eu não me importo muito com o desempenho - um PC médio desktop pode Quiete facilmente lidar com as tabelas de banco de dados com 100 milhões de linhas. Talvez leva cinco minutos, mas eu suponho que você não quer executar a tarefa a cada dois segundos.
Eu só fiz um teste. I gerou uma lista com 15.000 prefixos exclusivos com 5 a 10 dígitos. A partir deste prefixos I gerados 50.000 números com um prefixo e adicional de 5 a 10 dígitos.
List<String> prefixes = GeneratePrefixes();
List<String> numbers = GenerateNumbers(prefixes);
Então eu usei a seguinte consulta LINQ to Object para encontrar o prefixo de cada número.
var numberPrefixes = numbers.Select(n => prefixes.First(n.StartsWith)).ToList();
Bem, demorou cerca de um minuto no meu Core 2 Duo laptop com 2,0 GHz. Então, se um tempo de processamento minutos é aceitável, talvez dois ou três, se você incluir a agregação, eu não tentar otimizar nada. Claro, seria realmente bom se o Programa poderia fazer a tarefa em um segundo ou dois, mas isto irá adicionar um pouco de complexidade e muitas coisas para errar. E é preciso tempo para design, escrita e teste. A declaração LINQ pegou minhas apenas alguns segundos.
Aplicação de Teste
Note que a geração de muitos prefixos é muito lento e pode demorar um minuto ou dois.
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; }
}
}
}
Outras dicas
Parece-me que você precisa para construir um trie dos prefixos de operadoras. Você vai acabar com um único trie, onde os nós de terminação dizer a transportadora para esse prefixo.
Em seguida, criar um dicionário de transportador para um ou int long (total).
Em seguida, para cada linha número discado, apenas trabalhar o seu caminho no trie até encontrar a transportadora. Encontre o número total de minutos até agora para a transportadora, e adicione a linha atual -., Em seguida, seguir em frente
A estrutura de dados mais fácil que faria isso bastante eficiente seria uma lista de sets. Fazer um conjunto para cada operadora para conter todos os prefixos.
Agora, para associar uma chamada com um portador:
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;
}
Se você tem 10 operadoras, haverá 70 pesquisas em conjunto por chamada. Mas uma pesquisa em um conjunto não é muito lento (muito mais rápido do que uma busca linear). Portanto, este deve dar-lhe bastante um grande velocidade ao longo de uma força bruta linear de busca.
Você pode ir um passo além e agrupar os prefixos para cada portadora de acordo com o comprimento. Dessa forma, se um portador tem apenas prefixos de comprimento 7 e 4, você sabe apenas se preocupam em extrair e procurar esses comprimentos, cada vez que olhar no conjunto de prefixos desse comprimento.
Como cerca de despejar seus dados em um par de tabelas de banco de dados e, em seguida, consulta-los usando SQL? Fácil!
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
(Isto foi escrito para o SQL Server, mas deve ser muito simples para traduzir para outros DBMS.)
Talvez seria mais simples (não necessariamente mais eficiente) a fazê-lo em um banco de dados em vez de C #.
Você pode inserir as linhas no banco de dados e na inserção determinar a transportadora e incluí-lo no registro (talvez em um disparador de inserção).
Em seguida, o relatório seria uma consulta soma na tabela.
Eu provavelmente só colocar as entradas em uma lista, classificá-lo, em seguida, usar um binário procurar para procurar correspondências. Tailor os critérios de pesquisa jogo binários para retornar o primeiro item que corresponde, em seguida, iterate ao longo da lista até encontrar um que não corresponde. A busca binária leva apenas cerca de 15 comparações para procurar uma lista de 30.000 itens.
Você pode querer usar um HashTable em C #.
Desta forma, você tem pares chave-valor, e suas chaves poderiam ser os números de telefone, e seu valor o total de minutos. Se for encontrada uma correspondência no conjunto de chaves, em seguida, modificar o total de minutos, caso contrário, adicione uma nova chave.
Você, então, só precisa modificar seu algoritmo de busca, não olhar para toda a chave, mas apenas os primeiros 7 dígitos do mesmo.
