3 ms·
I initially thought this as well, but reading the code showed me it's actually O(1) to add each item to the set. Each cell computes in parallel (new_data < cel
by lightcatcher 11y ago
I initially thought this as well, but reading the code showed me it's actually O(1) to add each item to the set.
Each cell computes in parallel (new_data < cell_data) & (cell_state == OCCUPIED). If this is true, then the cell will be pushed down, either be the new data or by the data from the cell above. Each cell can also grab this value from the cell above. If the cell above's value is true, then the cell grabs the value from the cell above. If the value in the cell above is false, then the cell grabs the data being inserted. This is O(1) because there's no cascading value shift. I personally found this pretty clever, and I'm looking forward to implementing some of these bounded size hardware sorts on GPU.
- deleted 11y ago[deleted]
- mabbo 11y ago> Each cell can also grab this value from the cell above Therein lies the problem I see. Grabbing this value from the above cell implies that this value has already been calculated- but it hasn't, as these cells run in parallel. The results of a cell in a single round of calculations is not accessible to the other cells during the same round. In short- how does a cell know whether its new value is the value being inserted or the value being pushed down without knowing the result of the cell above it? And having asked that, I can actually think of one answer: it can calculate whether it's neighbor will be pushing or not independently. So each cell is really doing the calculation of "given these two numbers (my cell's value and the above cell's), where does this new number fit in sorted order with them- before, between, or after".