通過具有可變列數的CSV進行搜索

我可以使用一些幫助來思考我正在解決的難題。我打算用Ruby來解決它，但可以使用另一種語言，如Javascript/Node。我需要幫助解決問題和設計。通過具有可變列數的CSV進行搜索

我目前正在研究一個命令行程序，該程序讀取CSV數據，根據參數搜索CSV，然後根據查找結果生成輸出。

CSV行具有兩種格式之一。一個很簡單的餐館，食品，它們的價格列表：

restaurant ID, price, item label

但對於餐館提供組合餐，那裏可以在超值套餐任意數量的項目：

restaurant ID, price, item 1 label, item 2 label, ...

所以這個想法是，你可以運行這個程序，用CSV文件的參數來讀取你想吃的食物，並且它輸出他們應該去的餐廳，以及它將花費的總價格。只要總成本最小化，就可以購買額外的物品。

樣品data.csv

1, 4.00, burger 
1, 8.00, tofu_log 
2, 5.00, burger 
2, 6.50, tofu_log 

$ foodfinder.rb data.csv burger tofu_log 
=> 2, 11.5

與具有多個食品行

同樣：

5, 4.00, extreme_fajita 
5, 8.00, fancy_european_water 
6, 5.00, fancy_european_water 
6, 6.00, extreme_fajita, jalapeno_poppers, extra_salsa 

$ foodfinder.rb data.csv fancy_european_water extreme_fajita 
=> 6, 11.0

由於數據規範化是不是一種選擇，我不能將這些推到DB - 我想知道如何去思考如何高效地解析CSV。此外，一些行有多個食品項目，我不確定如何存儲這些。我猜想我想將行導入到散列中，然後以某種方式搜索散列。任何指導，巫師？

來源

2013-11-15 Sean Knox

如果CSV具有標準，則該文件不遵守它。 – RyPeck

@RyPeck：有各種CSV標準，但沒有人注意它們:) –

同意CSV格式是可怕的！儘管挑戰的一部分是清理數據。 –

這些數據很容易與標準CSV library和扯皮陣列的一點點解析：在data

data = CSV.open('data.csv') 
      .map { |r| [ r[0], r[1], r[2..-1].map(&:strip) ] }

這就給了你這樣的：

data = [ 
    ['5', '4.00', ['extreme_fajita']], 
    ['5', '8.00', ['fancy_european_water']], 
    #... 
]

從那裏，它是很容易建立無論您需要什麼索引結構。

但是，如果你在尋找'extra_salsa'行只是感興趣，然後使用select代替map：

want = CSV.open('x.csv') 
      .select { |r| r[2..-1].map(&:strip).include?('extra_salsa') }

和清理want打印但是您需要。

每當腳本運行時，您都會旋轉整個CSV文件，因此您應該在掃描時搜索它，構建中間索引數據結構只是浪費時間，如果您只做一個每次運行搜索。

來源

2013-11-15 22:43:47

對於Ruby，我會跳過標準的CSV庫，只加載行，將它們分割成至多三塊，然後將第三行轉換爲數組。從這一點來說，你有你所需要的：

records = file.map { |row| 
    row.split(/,\s?/, 3) 
}.map { |arr| 
    [arr[0].to_i, arr[1].to_f, arr[2].split(/,\s?/)] 
}

現在，您的記錄將是：

[ 
    [5, 4.00, ["extreme_fajita"]], 
    [5, 8.00, ["fancy_european_water"]], 
    [6, 5.00, ["fancy_european_water"]], 
    [6, 6.00, ["extreme_fajita", "jalapeno_poppers", "extra_salsa"]] 
]

您可以使用上解決這一數據NP完全問題的知識，一個已經需要的形式。

來源

2013-11-15 22:13:41 rewritten

我會考慮甚至不解析CSV數據開始。只需grep用所需字符串的行，然後用你的方式解析它。會更快。 – Casper

這個解析步驟非常快，'grep'不會有太大的收穫。真正困難的問題是要找到最佳覆蓋範圍，因爲只要您足夠深入地分析問題，您就會發現。 – rewritten

因此，對於每個restaurnat你必須找到（如果有的話）與最低價格的組合，如果它們的聯合滿足你的需求。這是NP完全問題。任意子集的最優覆蓋。 – rewritten

通過具有可變列數的CSV進行搜索

回答

相關問題