Come faccio a sapere rapidamente se un elenco contiene un elenco?

StackOverflow https://stackoverflow.com/questions/4192961

Domanda

Ci sono diverse questioni connesse, ma sto cercando una soluzione specifica per il mio caso. C'è una serie di (di solito) 14 numeri interi, ciascuno nella gamma da 1 a 34. Come faccio a sapere rapidamente se ogni int in una specifica lista statica appare almeno una volta in questo array?

Per riferimento, Attualmente sto usando questo codice, che è stato scritto per assomigliare la specifica più vicino possibile, in modo che possa certamente essere migliorata notevolmente: 

if (array.Count < 13) {
    return;
}

var required = new int[] {
    0*9 + 1,
    0*9 + 9,
    1*9 + 1,
    1*9 + 9,
    2*9 + 1,
    2*9 + 9,                
    3*9 + 1,
    3*9 + 2,
    3*9 + 3,
    3*9 + 4,
    3*9 + 5,
    3*9 + 6,
    3*9 + 7,
};

IsThirteenOrphans = !required.Except (array).Any ();

L'elenco richiesta non è dinamica, cioè esso sarà sempre la stessa durante il funzionamento. Utilizzando LINQ è facoltativo, l'aspetto principale è la prestazione.

Modifica

  • La matrice di input non è ordinato.
  • I valori di input possono apparire più volte.
  • La matrice di input conterrà almeno 14 elementi, vale a dire più di 1 dell'array richiesto.
  • C'è solo 1 campo richiesto ed è statico.
  • I valori richiesti sono distinti.
  • Si può supporre che un istogramma è a buon mercato per creare.

Aggiornamento:. Sono anche interessato a una soluzione per un array di input ordinato

È stato utile?

Soluzione

Idea 1
Se avete bisogno di confrontare con diverse liste required allora si potrebbe ordinare la lista di ingresso e poi semplicemente confrontarlo da iterazione. Ma l'ordinamento è, naturalmente, non troppo veloce, ma neanche troppo lente. Ma se si confronta con diverse liste richiesti il ??sovraccarico di ordinamento potrebbe essere ammortizzato rapidamente.

Una volta che l'array è ordinato il confronto è banale: 

for(int i = 0; i < 14; i++)
  if(arr[i] != required[i]) return false;

return true;

Idea 2
O se i 14 interi sono distinti / unici si può semplicemente fare un required HashSet e fanno 

input.Count(i => required.Contains(i)) == 14

Ma io non lo so, senza in realtà il test se questo è più veloce di smistamento.

Idea 3
Calcolare un hash breve che è invariante permutazioni oltre i 14 int e confrontarlo con il valore noto di require. Solo se le partite hash fanno il paragone più costosi. 

//Prepare/precalculated
int[] hashes = new int[34];
Random random = new Random();
for(int i = 0; i < 34; i++)
  hashes[i] = random.NextInt();

//On each list
int HashInts(int[] ints)
{
  int result = 0;
  foreach(int i in ints)
    result += hashes[i - 1];

  return result;
}

Una scelta saggia di valori per hashes potrebbe migliorare un po ', ma i valori casuali dovrebbe andare bene.

Idea 4
Creare un Istogramma: 

int[] CreateHistogram(int[] ints)
{
  int[] counts = new int[34];
  foreach(int i in ints)
  {
    counts[i - 1]++;
  }

  return counts;
}

È possibile evitare la matrice di creare riutilizzando un array esistente se le prestazioni sono davvero importante.

Altri suggerimenti

Se ha un 34+ bit tipo integrale disponibile, e stile C operazioni a bit, allora si potrebbe calcolare un tale intero V dall'elenco delle variabili (se l'elenco è v [0], v [1], ... allora v è (1 << v [0]) | (1 << v [1]) ... dove 1 è dello stesso tipo v) e hanno un numero intero tale predefinita S per l'elenco statico, calcolato analogamente. Il test per verificare se l'elenco statico è contenuta nell'elenco delle variabili è quindi (S & ~ V) == 0.

Una possibilità è quella di cambiare il modo in cui si memorizzano i dati. Dal momento che la gamma dei possibili valori è limitato a 1-34, invece di memorizzare un elenco di numeri, è possibile memorizzare i conteggi di ogni numero presente: 

int[] counts = new int[34];

Se la lista ha un 1 e due 3s, poi conta [0] == 1 && conta [2] = 2 (si potrebbe in alternativa utilizzare l'indicizzazione 1-based se questo fa le cose più velocemente (meno sottrazioni.))

Ora per valutare che ogni int in un elenco appare almeno una volta, è sufficiente indice nella matrice in sequenza per ogni x e verificare che tutti i conteggi [x]> 0. Ci saranno overhead associato alla trasformazione dei dati dai conti modulo per la forma di lista, ma questo è solo un problema se anche spesso bisogno di visualizzare i dati in forma di elenco. Un altro vantaggio di questo formato di archiviazione è che l'aggiunta / rimozione di conteggi sarà mai coinvolgere più di un singolo elemento dell'array; in forma di elenco, rimozione di un elemento nel mezzo della lista comporta una copia di più elementi.

Se si desidera modo veloce non si dovrebbe usare LINQ, se una data voci di elenco tutti sono muggito 35 è possibile rimuovere if (lst[i] < 35) L'elenco traversata soffietto risposta al massimo una sola volta, e si comporta come counting sort : 

public bool FindExactMatch(int[] array, List<int> lst)
{
    bool[] a34 = new bool[35];

    foreach(var item in array)
    {
        a34[item] = true;
    }

    int exact = 0;

    for (int i = 0; i < lst.Count; i++)
    {
        if (a34[lst[i]])
        {
            exact++;
            if (exact == array.Length) return true;

            a34[lst[i]] = false;
        }
    }

    return false;
}

per lista ordinata se la dimensione elenco è grande si può fare lst.BinarySearch(array[i]) che prende 14 * log (n) * c1 al massimo, e penso che sia abbastanza efficace anche se si implementa si può diventare più veloce, e non ho la prova ricerca binaria con la mia propria implementazione, ma Min, Max, Sort in LINQ è più lento (tra 4 e 10 di tempo) il proprio (buono) implementazione. E se la dimensione lista ordinata è piccolo io preferisco usare l'algoritmo come sopra, perché costante c1 è di piccole algoritmo di cui sopra e può essere più grande in algoritmo di ricerca binaria.

Questo appare come un buon candidato per operazioni bit per bit, dato che i valori richiesti sono distinti, statico, e tra 1 e 34. Invece di risparmio richiesto come un array, salva come const ulong. Negli array per controllare, creare un nuovo ulong popolato da sinistra-shift ogni valore e bit a bit o. 

const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34);

public static bool ContainsDistinct13Values(int[] array)
{
    ulong word = 0;
    foreach (int i in array)
    {
        word |= (1UL << i);
    }
    return word == comparator;
}

Modifica Così ho capito la tua domanda e probabilmente qualche bella soluzione troppo complicata. Un'altra domanda è, come buona prestazione che ha. 

static void Main(string[] args)
{
    var required = new int[]
                       {
                           0*9 + 1,
                           0*9 + 9,
                           1*9 + 1,
                           1*9 + 9,
                           2*9 + 1,
                           2*9 + 9,
                           3*9 + 1,
                           3*9 + 2,
                           3*9 + 3,
                           3*9 + 4,
                           3*9 + 5,
                           3*9 + 6,
                           3*9 + 7,
                       };

    precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset);

    for (int i = 0; i < required.Length; i++)
    {
        precomputedResult |= (UInt16)(1 << i);
    }

    int[] array = new int[34]; // your array goes here..
    Console.WriteLine(ContainsList(array));

    Console.ReadKey();
}

// precompute dictionary
private static Dictionary<int, UInt16> precomputed;
// precomputed result
private static UInt16 precomputedResult = 0;

public static bool ContainsList(int[] values)
{
    UInt16 result = 0;
    for (int i = 0; i < values.Length; i++)
    {
        UInt16 v;
        if (precomputed.TryGetValue(values[i], out v))
            result |= v;
    }

    return result == precomputedResult;
}

Si potrebbe facilmente ciclo tra gli elementi e scoprire c'è qualche articolo mancante. Con il vostro esempio ho capito che si voleva solo sapere se c'è qualche elemento dalla richiesto risulta mancante in array. così si potrebbe scrivere 

bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;
    }

    if (notContains == false) break;
}

Questo è molto più veloce di quanto il vostro approccio. Controlla il codice qui sotto con il timer aggiunto. Il tuo approccio preso 5 ms, ma quello nuovo prendere 0 ms 

System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch();
aTimer.Start();

var IsThirteenOrphans = !required.Except(array).Any();
aTimer.Stop();

System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch();
bTimer.Start();
bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;            
    }

    if (notContains == false) break;
}

bTimer.Stop();
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top