在一個稀疏的Javascript數組上執行查找

我有一個有趣的Javascript任務（在Node.js中執行，FWIW）：我需要將我有值的數據集的「加權中值」（在本例中爲收入）併爲每一個重量。例如：在一個稀疏的Javascript數組上執行查找

income #people 
0 5 
16000 3 
20000 8 
32000 4 
40000 3 
41000 1 
50000 2 
90000 1

換句話說，8人做$ 20K，2使$ 50K，等我需要的「加權中值」 - 所有27人的中位數。

天真的方式做，這將是使一個數組，並與每個值種子它，就像這樣：然後

var incomes = [0, 0, 0, 0, 0, 16000, 16000, 16000, 20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000, 32000, 32000, 32000, 32000, 40000, 40000, 40000, 41000, 50000, 50000, 90000];

人們可以很容易利用這個數組的中位數（即$ 20,000）。事實上，我有每個樣本7000到14000人的數據。雖然我確信Node可以處理這麼大的數組，但感覺令人難以置信的馬虎。

我目前的解決方案是計算假設詳細數組中的中值的索引-13，在這種情況下 - 以及通過收入和權重數組的循環，累加累計重量直到達到或超過中途點。這是一個簡單的例子。（顯然，中位數需要偶數名單略有不同的規則。這只是一個POC）。

var halfway = 13, 
    progress = 0; 

var vals = [[0,5], [16000,3], [20000,8], [32000,4], [40000,3], [41000,1], [50000,2], [90000,1]]; 

for (var v = 0; v < vals.length; v += 1) { 
    progress += vals[v][1]; 

    if (progress >= halfway) { 
     var median = vals[v][0]; 
     break; 
    } 
}

這工作正常，但是當你要開始計算位數和等它就會變得混亂。更容易的是，我可以在冗餘數組的適當位置創建一個稀疏數組而不填寫所有中間值，然後在該數組上查找任何最大值的索引。但是我需要一些有效的機制來查找稀疏數組中的前一個已知索引，如果（可能）我在備用數組中查找的索引沒有填充。

這似乎是一個相當普遍的問題。

來源

2014-09-24 Chris Wilson

愚蠢的問題，但：你有沒有嘗試過'vals.forEach（function（element，i，array）{}）;' – DrakaSAN 2014-09-24 15:30:12

不知道這會做什麼不同於循環舊式的方式，就像我上面做的。（我這樣做是因爲它更容易擺脫。） – 2014-09-24 15:35:27

您需要處理多少個不同的收入？成千上萬的人中有很多人會有不同的收入嗎？ – parchment 2014-09-24 15:41:17

在計算效率方面，我認爲你所擁有的就像你將會得到的那樣好，儘管我不確定你的四分位數面對哪些困難（對不起，代表太低請求澄清）。

讓我們先看看你有什麼效率。你有一個長度爲n的數組，你通過它添加到一個計數器並中途中斷（我假設給出了中途信息，再次抱歉太低而不能提問）。所以不錯，看着一個簡單的O（n）。

現在你提出的是某種形式的查詢，給定一個索引知道最近的人口指數，O（1）。那樣會更好，所以讓我們看看我們需要什麼。那麼我們需要通過循環來將給定的數據移動到一個新的數據結構中......哦，這意味着OOP返回到O（n）。

道德故事你有什麼是好的，好的工作。

來源

2014-09-24 21:16:52 neverlucky13

在一個稀疏的Javascript數組上執行查找

回答

相關問題