ein Array von ganzen Zahlen gegeben, die Größe des Arrays mit annähernd gleichen Abständen

Question

eine Reihe von Zahlen wie folgt gegeben:

[0, 99, 299, 498, 901] 

Welche Algorithmus konnte ich mit etwa gleichen Abständen zwischen ihnen das Array in ein Array die Größe verwenden. Oder anders gesagt, resample mit ungefähren größten gemeinsamen Vielfachen. So mit dem obigen Beispiel dem größten gemeinsamen Teiler ist etwa 100, so wäre das Ergebnis:

[0, 99, 200, 299, 400, 498, 600, 700, 800, 901] 

die ursprünglichen Werte verwenden wäre schön, und Fehlerbalken können eingestellt werden (siehe oben Lösung 2 Fehler gesetzt hat

[0, 100, 200, 300, 400, 500, 600, 700, 800, 900]

Aktualisieren 12 Jan 2017

:), sondern auch mit diesem Ergebnis zufrieden sein Basierend auf Antwort Redu ist, hier ist die Swift-Version seines Code:

var arr: [Int] = [0, 99, 299, 498, 901] 

var diffs = [Int]() 
var minGap: Int = 0 
for x in 0..<arr.count-1 { 
    let gap = arr[x+1] - arr[x] 
    diffs.append(gap) 
    if minGap == 0 || minGap > gap { 
     minGap = gap 
    } 
} 

var resamples = [Int]() 
for item in arr { 
    if let lastSample = resamples.last { 
     let n = Int((Float(item - lastSample)/Float(minGap)).rounded()) 
     let g = (item - lastSample)/n 
     var inserts = [Int]() 
     for x in 0..<n-1 { 
      let newSample = lastSample + ((x+1) * g) 
      inserts.append(newSample) 
     } 
     resamples.append(item) 
     resamples.append(contentsOf: inserts) 
    } else { 
     resamples.append(item) 
    } 
} 

Answer 1

Das folgende wäre meine Lösung in JS. Ich finde zuerst die minimale Lücke und versuche dann herauszufinden, wie viele davon zwischen die einzelnen Elemente passen würden, ohne die ursprünglichen Werte zu verändern.

Offensichtlich muss das Eingabearray für diesen Algorithmus aufsteigend sortiert sein.

var arr = [0, 99, 299, 498, 901], 
 
    gap = Math.min(...Array(arr.length-1).fill().map((_,i) => arr[i+1]-arr[i])), // Find the minimum gap 
 
    res = arr.reduce((p,c,i) => { var n = Math.round((c-p[p.length-1])/gap);  // Find howmany gaps are inbetween according to the minimum gap 
 
             g = Math.round((c-p[p.length-1])/n);  // Calculate the average gap top apply 
 
            return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c) 
 
              : p.concat(c); 
 
           },[]); 
 
console.log(res);

Erläuterung:

gap = Math.min(...Array(arr.length-1).fill().map((_,i) => arr[i+1]-arr[i])), 

Zuerst setzen wir ein neues Array in der Größe eins kleiner als die Eingangsanordnung auf. (Array(arr.length-1)) initialisieren wir zuerst() es mit undefinierten Elementen und dann .map() jedes Element mit arr[i+1]-arr[i]. So, jetzt haben wir die Lücke Array. Dann haben wir es in eine Math.min() Funktion als Argumente verteilt. Es ist der Math.min(...Array( Teil. Jetzt haben wir die minimale Lücke als 99 im oben genannten Fall.

.reduce() Teil ist etwas hart aussehend, aber es ist einfach. Unsere Operation .reduce() übernimmt eine Funktion als Argument (meist als Callback-Funktion bezeichnet) und führt sie bei jeder Iteration über die Array-Elemente aus. Diese Callback-Funktion ist der Teil, der mit (p,c,i) => {... } beginnt. Dies ist eine Pfeilfunktion. Was im Wesentlichen mit normalen Funktionen identisch ist. x => x bedeutet function(x) { return x;} oder x => {return x;}. In unserem Fall, da wir Klammern verwenden, um den Körper unserer Funktion zu definieren (aufgrund mehrerer Anweisungen), müssen wir eine return Anweisung verwenden.

Unser .reduce() verwendet einen Anfangswert, der ein leeres Array ist. Es ist der ,[]); Teil am Ende. Die Callback-Funktion, die reduces pro Array-Element aufruft, wird an drei Argumente übergeben. (p,c,i) Das anfängliche leere Array wird dem p-Argument (vorhergehend) zugewiesen, das aktuelle Element wird dem c-Argument zugewiesen und der aktuelle Index wird dem i zugewiesen Argument pro Aufruf.

In unserem Callback definieren wir 2 Variablen. n und g.

n = Math.round((c-p[p.length-1])/gap); 

p[p.length-1] gibt das letzte Element des p Array. Also in der ersten Runde; Wenn i = 0, p[0] ist undefined und Math.round((c-p[p.length-1])/gap); ist ein NaN (keine Nummer), aber uns egal, weil;

return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c) 
     : p.concat(c); 

Die ternäre Bedingung bedeutet, dass;

result = condition ? if true do this 
        : if false do this 

So wie Sie sehen, abhängig von der Bedingung tut es eine der Anweisungen und gibt das Ergebnis zurück. In unserem Fall wird das Ergebnis als Wert zurückgegeben.

Also in unserem Fall, wenn i == 0 (false Wert in JS) dann tut nur p.concat(c) und gibt den neuen p Wert und fahren Sie mit der nächsten Iteration (aufrufen Rückruf mit den neuen p, c und i Werten.

Wenn i nicht false ist (jeder Wert ungleich 0), dann gefällt

p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c) 

, die eine Anordnung in der Größe, um die Lücke viele Zwischenelemente aufzunehmen bedeutet zu schaffen, Initi alize das Array mit undefineds und jedes Element mit p[p.length-1] + (i+1)*g abbilden und dieses Array mit dem p Array verbinden und c bis zum Ende anhängen und dann das p Array zurückgeben.

Eine Sache zu erinnern: p.concat(whatever...) Anweisung würde ein neues Array, bestehend aus den Elementen und die "Elemente" der Arrays als Argument enthalten oder die Elemente selbst enthalten ar Argument zurückgeben. Ich meine;

[1,2,3].concat([4,5,6],[7,8],9) würde [1,2,3,4,5,6,7,8,9]

es also sollte dies erklären.

Answer 2

Im Grunde wollen Sie eine Regression der kleinsten Quadrate gegen eine arithmetische Progression verwenden.

Eine arithmetische Progression kann mit 3 Termen parametrisiert werden: erster Term, letzter Term und gemeinsamer Unterschied. Diese 3 Begriffe würden die Parameter Ihrer Zielfunktion bilden, die Sie minimieren möchten.

In jedem Optimierungsschritt müssen Sie auswählen, welche Begriffe in der arithmetischen Progressionsprozedur gegenüber Ihrer ursprünglichen Menge regressiert werden müssen. Das wird ziemlich schwierig sein, aber glücklicherweise werden beide Serien sortiert, so dass dies ein O (N) Traversal sein sollte.

Eine Beschränkung um die 3 Begriffe wäre eine typografisch ansprechende Menge. Wären beispielsweise 100, 200, 300 gegenüber 99, 198, 297 bevorzugt, selbst wenn die Quellenserie 99, 297 & ge;

Eine vollständige Antwort würde ich fühle zu breit sein - und ist wahrscheinlich mindestens eine Woche Arbeit. Aber so würde ich das Projekt beginnen.