top | item 11625165

(no title)

za_creature | 9 years ago

Not disappointing at all; solving the system in a least-squares sense is O(n^3) and choosing the optimal setup is NP-complete (didn't prove it, but I'm _pretty_ sure it involves backtracking, especially when you consider stuff like adding a PCIe SATA controller to maximize the total amount of storage available).

I originally wanted to monetize the idea as well, but gave up and open sourced my solution due to the labor-intensiveness of adding and maintaining components and benchmarks.

I can't really help you business-wise, but from a technical standpoint, my suggestion would be to split up the problem in two (sorry for the formal definitions, this is mostly translated from my paper):

1. Given n benchmarks each containing n[i] components each, assign a score to each component so as to obtain a total ordering that minimizes the error (as you mentioned above, one processor may be _way_ faster than another in one benchmark, but be completely outclassed in 50 others).

2. Given n desired component classes, each containing n[i] components as well as their bus requirements or offerings (I stretched the 'bus' definition to also include stuff like S-ATA, 3.5'' slots, ATX power cables, etc), their performance relative to components of the same class (obtained at step 1) and their price, obtain a compatible component subset that:

i) satisfies sum(Price[i]) < max_price

ii) satisfies sum(Power[i]) > 0 (assuming PSUs provide positive power and everything else negative power; I used watts here but if you're feeling badass, you can extend this to amps on the 3.3 / 5 / 12V rails)

iii) maximizes weighted-sum(Performance[i]), given a certain target (this is how I implemented the "I don't want to play games" feature requested by another HN poster; in this case, each target would define a weight for each component class)

Since 2. is most likely NP-complete (again, didn't prove it), my approximate solution was a greedy PTAS knapsack ( https://en.wikipedia.org/wiki/Knapsack_problem ) that stored partial systems in one of 3 heaps of about 10k items each: one sorted by cost (to ensure the cheapest system is displayed in the event of a low budget), one sorted by performance (to ensure the best system is displayed, in the event of a high budget) and one sorted by performance/cost ratio (to hopefully obtain the best-bang-for-your-buck system).

Anyway, best of luck! Throw me a tweet (same username as HN) if you make it big :)

discuss

order

No comments yet.