Eficiente mesclar matrizes de cadeia em .NET, mantendo valores distintos
https://stackoverflow.com/questions/146358
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou usando .NET 3.5. Eu tenho duas matrizes de cadeia, que podem compartilhar um ou mais valores:
string[] list1 = new string[] { "apple", "orange", "banana" };
string[] list2 = new string[] { "banana", "pear", "grape" };
Eu gostaria de uma maneira de fundi-los em uma variedade sem valores duplicados:
{ "apple", "orange", "banana", "pear", "grape" }
Eu posso fazer isso com o LINQ:
string[] result = list1.Concat(list2).Distinct().ToArray();
mas imagino que não é muito eficiente para grandes matrizes.
Existe uma maneira melhor?
Solução
string[] result = list1.Union(list2).ToArray();
MSDN : "Este método exclui duplicatas do conjunto de retorno . Este é um comportamento diferente para o método Concat (TSource), que retorna todos os elementos nas sequências de entrada, incluindo duplicações ".
Outras dicas
Por que você imagina que seria ineficiente? Tanto quanto eu estou ciente, tanto Concat e distintas são avaliados preguiçosamente, usando um HashSet nos bastidores para distintos para manter o controle dos elementos que já foram devolvidos.
Eu não sei como você consegue torná-lo mais eficiente do que de um modo geral:)
EDIT: Distinct realmente usa Set (uma classe interna) em vez de HashSet, mas a essência ainda está correto. Este é realmente um bom exemplo de quão puro LINQ é. A resposta mais simples é praticamente tão eficiente quanto você pode conseguir sem mais conhecimento de domínio.
O efeito é o equivalente a:
public static IEnumerable<T> DistinctConcat<T>(IEnumerable<T> first, IEnumerable<T> second)
{
HashSet<T> returned = new HashSet<T>();
foreach (T element in first)
{
if (returned.Add(element))
{
yield return element;
}
}
foreach (T element in second)
{
if (returned.Add(element))
{
yield return element;
}
}
}
.NET 3.5 introduziu a classe HashSet que poderia fazer isso:
IEnumerable<string> mergedDistinctList = new HashSet<string>(list1).Union(list2);
Não tenho certeza do desempenho, mas deve bater o exemplo Linq que você deu.
EDIT: Eu estou corrigido. A implementação preguiçoso de Concat e distinto tem uma memória chave e vantagem de velocidade. Concat / distinta é cerca de 10% mais rápido, e salva várias cópias de dados.
I confirmada através de código:
Setting up arrays of 3000000 strings overlapping by 300000
Starting Hashset...
HashSet: 00:00:02.8237616
Starting Concat/Distinct...
Concat/Distinct: 00:00:02.5629681
é a saída:
int num = 3000000;
int num10Pct = (int)(num / 10);
Console.WriteLine(String.Format("Setting up arrays of {0} strings overlapping by {1}", num, num10Pct));
string[] list1 = Enumerable.Range(1, num).Select((a) => a.ToString()).ToArray();
string[] list2 = Enumerable.Range(num - num10Pct, num + num10Pct).Select((a) => a.ToString()).ToArray();
Console.WriteLine("Starting Hashset...");
Stopwatch sw = new Stopwatch();
sw.Start();
string[] merged = new HashSet<string>(list1).Union(list2).ToArray();
sw.Stop();
Console.WriteLine("HashSet: " + sw.Elapsed);
Console.WriteLine("Starting Concat/Distinct...");
sw.Reset();
sw.Start();
string[] merged2 = list1.Concat(list2).Distinct().ToArray();
sw.Stop();
Console.WriteLine("Concat/Distinct: " + sw.Elapsed);
Aviso Esta é a otimização prematura. Por seu exemplo matrizes, use os 3,5 métodos de extensão. Até que você sabe que tem um problema de desempenho nesta região, você deve usar o código da biblioteca.
Se você pode classificar as matrizes, ou estão classificadas quando você chegar a esse ponto no código, você pode usar os seguintes métodos.
Estes irão puxar um item de ambos, e produzir o "menor" item, em seguida, buscar um novo item da fonte correspondente, até que ambas as fontes estão esgotados. No caso em que o item atual obtido a partir das duas fontes são iguais, que irá produzir a partir da primeira fonte, e ignorá-los em ambas as fontes.
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2)
{
return Merge(source1, source2, Comparer<T>.Default);
}
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2, IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source1))
throw new ArgumentNullException("source1");
if (Object.ReferenceEquals(null, source2))
throw new ArgumentNullException("source2");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T>
enumerator1 = source1.GetEnumerator(),
enumerator2 = source2.GetEnumerator())
{
Boolean more1 = enumerator1.MoveNext();
Boolean more2 = enumerator2.MoveNext();
while (more1 && more2)
{
Int32 comparisonResult = comparer.Compare(
enumerator1.Current,
enumerator2.Current);
if (comparisonResult < 0)
{
// enumerator 1 has the "lowest" item
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
else if (comparisonResult > 0)
{
// enumerator 2 has the "lowest" item
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
else
{
// they're considered equivalent, only yield it once
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
more2 = enumerator2.MoveNext();
}
}
// Yield rest of values from non-exhausted source
while (more1)
{
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
while (more2)
{
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
}
}
Note que, se uma das fontes contém duplicatas, você pode ver duplicatas na saída. Se você deseja remover estes duplicados nas listas já classificadas, use o seguinte método:
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source)
{
return CheapDistinct<T>(source, Comparer<T>.Default);
}
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source,
IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source))
throw new ArgumentNullException("source");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T> enumerator = source.GetEnumerator())
{
if (enumerator.MoveNext())
{
T item = enumerator.Current;
// scan until different item found, then produce
// the previous distinct item
while (enumerator.MoveNext())
{
if (comparer.Compare(item, enumerator.Current) != 0)
{
yield return item;
item = enumerator.Current;
}
}
// produce last item that is left over from above loop
yield return item;
}
}
}
Note que nenhum destes vai usar internamente uma estrutura de dados para manter uma cópia dos dados, de modo que será mais barato se a entrada está classificada. Se você não pode, ou não, garantia de que, você deve usar os 3,5 métodos de extensão que você já encontrou.
código de exemplo aqui que chama os métodos acima:
String[] list_1 = { "apple", "orange", "apple", "banana" };
String[] list_2 = { "banana", "pear", "grape" };
Array.Sort(list_1);
Array.Sort(list_2);
IEnumerable<String> items = Merge(
CheapDistinct(list_1),
CheapDistinct(list_2));
foreach (String item in items)
Console.Out.WriteLine(item);
Provavelmente a criação de uma tabela hash com os seus valores como chaves (somente adicionando aqueles que não estão já presentes) e, em seguida, converter as chaves para uma matriz poderia ser uma solução viável.
Você não sabe qual abordagem é mais rápido até que você medi-lo. A maneira LINQ é elegante e fácil de entender.
Outra maneira é implementar um conjunto como uma matriz de hash (dicionário) e adicionar todos os elementos de ambas as matrizes para o conjunto. Em seguida, utilizar o método set.Keys.ToArray () para criar a matriz resultante.
