Einfachste Code für Array Schnittpunkt in Javascript

Question

Was ist die einfachste, Bibliothek-freien Code für die Umsetzung von Array-Kreuzungen in Javascript? Ich möchte schreiben

intersection([1,2,3], [2,3,4,5])

und erhalten

[2, 3]

Answer 1

function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
    for (j=0; j<B.length; j++) {
        if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
            result.push(A[i]);
        }
    }
}
return result;
}

Answer 2

Ich habe eine intesection Funktion geschrieben, die sogar Schnittpunkt von Array von Objekten basierend auf bestimmten Eigenschaft dieser Objekte erkennen kann.

Zum Beispiel,

if arr1 = [{id: 10}, {id: 20}]
and arr2 =  [{id: 20}, {id: 25}]

und wir wollen eine Kreuzung auf der Grundlage der id Eigenschaft, dann sollte die Ausgabe sein :

[{id: 20}]

Die Funktion dafür (Anmerkung: ES6-Code) ist :

const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
    const [fn1, fn2] = accessors;
    const set = new Set(arr2.map(v => fn2(v)));
    return arr1.filter(value => set.has(fn1(value)));
};

und Sie können die Funktion als aufrufen:

intersect(arr1, arr2, [elem => elem.id, elem => elem.id])

Beachten Sie auch, dass diese Funktion die Schnittmenge findet, wenn man davon ausgeht, dass das erste Array das primäre Array ist und somit das Ergebnis der Schnittmenge das des primären Arrays sein wird.

Answer 3

Der Einfachheit halber:

// Usage
const intersection = allLists
  .reduce(intersect, allValues)
  .reduce(removeDuplicates, []);

// Implementation
const intersect = (intersection, list) =>
  intersection.filter(item =>
    list.some(x => x === item));

const removeDuplicates = (uniques, item) =>
  uniques.includes(item) ? uniques : uniques.concat(item);

// Example Data
const somePeople = [bob, doug, jill];
const otherPeople = [sarah, bob, jill];
const morePeople = [jack, jill];

const allPeople = [...somePeople, ...otherPeople, ...morePeople];
const allGroups = [somePeople, otherPeople, morePeople];

// Example Usage
const intersection = allGroups
  .reduce(intersect, allPeople)
  .reduce(removeDuplicates, []);

intersection; // [jill]

Vorteile:

• ganz einfach
• datenzentriert
• funktioniert für eine beliebige Anzahl von Listen
• funktioniert für Listen beliebiger Länge
• funktioniert für beliebige Arten von Werten
• funktioniert für jede beliebige Sortierreihenfolge
• behält die Form bei (Reihenfolge des ersten Auftretens in einer Reihe)
• Frühzeitiger Ausstieg, wenn möglich
• speichersicherfest, ohne Manipulationen an Funktions-/Array-Prototypen

Nachteilig:

• höherer Speicherverbrauch
• höhere CPU-Nutzung
• erfordert ein Verständnis für die Reduzierung
• erfordert Verständnis des Datenflusses

Sie würden dies nicht für 3D-Engine oder Kernel-Arbeit verwenden wollen, aber wenn Sie Probleme haben, dies in einer ereignisbasierten Anwendung zum Laufen zu bringen, hat Ihr Design größere Probleme.

Answer 4

Ich werde mit dem beitragen, was für mich am besten funktioniert hat:

if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {

    var r = [], o = {}, l = this.length, i, v;
    for (i = 0; i < l; i++) {
        o[this[i]] = true;
    }
    l = arr1.length;
    for (i = 0; i < l; i++) {
        v = arr1[i];
        if (v in o) {
            r.push(v);
        }
    }
    return r;
};
}

Answer 5

Diese Funktion vermeidet das N^2-Problem und nutzt dabei die Möglichkeiten von Wörterbüchern. Die Schleife durchläuft jedes Array nur einmal, und eine dritte, kürzere Schleife liefert das Endergebnis. Außerdem unterstützt Zahlen, Strings und Objekte .

function array_intersect(array1, array2) 
{
    var mergedElems = {},
        result = [];

    // Returns a unique reference string for the type and value of the element
    function generateStrKey(elem) {
        var typeOfElem = typeof elem;
        if (typeOfElem === 'object') {
            typeOfElem += Object.prototype.toString.call(elem);
        }
        return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
    }

    array1.forEach(function(elem) {
        var key = generateStrKey(elem);
        if (!(key in mergedElems)) {
            mergedElems[key] = {elem: elem, inArray2: false};
        }
    });

    array2.forEach(function(elem) {
        var key = generateStrKey(elem);
        if (key in mergedElems) {
            mergedElems[key].inArray2 = true;
        }
    });

    Object.values(mergedElems).forEach(function(elem) {
        if (elem.inArray2) {
            result.push(elem.elem);
        }
    });

    return result;
}

Wenn es einen speziellen Fall gibt, der nicht gelöst werden kann, indem man einfach die generateStrKey Funktion könnte das Problem sicherlich gelöst werden. Der Trick bei dieser Funktion ist, dass sie die verschiedenen Daten nach Typ und Wert eindeutig darstellt.

---

Diese Variante hat einige Leistungsverbesserungen . Vermeiden Sie Schleifen, falls ein Array leer ist. Außerdem wird zuerst das kürzere Array durchlaufen. Wenn also alle Werte des ersten Arrays im zweiten Array gefunden werden, wird die Schleife verlassen.

function array_intersect(array1, array2) 
{
    var mergedElems = {},
        result = [],
        firstArray, secondArray,
        firstN = 0, 
        secondN = 0;

    function generateStrKey(elem) {
        var typeOfElem = typeof elem;
        if (typeOfElem === 'object') {
            typeOfElem += Object.prototype.toString.call(elem);
        }
        return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
    }

    // Executes the loops only if both arrays have values
    if (array1.length && array2.length) 
    {
        // Begins with the shortest array to optimize the algorithm
        if (array1.length < array2.length) {
            firstArray = array1;
            secondArray = array2;
        } else {
            firstArray = array2;
            secondArray = array1;            
        }

        firstArray.forEach(function(elem) {
            var key = generateStrKey(elem);
            if (!(key in mergedElems)) {
                mergedElems[key] = {elem: elem, inArray2: false};
                // Increases the counter of unique values in the first array
                firstN++;
            }
        });

        secondArray.some(function(elem) {
            var key = generateStrKey(elem);
            if (key in mergedElems) {
                if (!mergedElems[key].inArray2) {
                    mergedElems[key].inArray2 = true;
                    // Increases the counter of matches
                    secondN++;
                    // If all elements of first array have coincidence, then exits the loop
                    return (secondN === firstN);
                }
            }
        });

        Object.values(mergedElems).forEach(function(elem) {
            if (elem.inArray2) {
                result.push(elem.elem);
            }
        });
    }

    return result;
}