-2

I am running a process that uses lots of little queries to collect data. Then I sort the results and output a CSV file.

In the interest of multithreading, I'd like to sort the data at the time it is collected. Then when collection is done I can read the data out with O(1).

Does PHP have a data structure that supports this?

William Entriken
  • 37,208
  • 23
  • 149
  • 195
  • Mmm, not 100% sure what you are asking. If it's can PHP do mutlithreading then I think it's no not out the box. Here is agood question on the subject though. http://stackoverflow.com/questions/70855/how-can-one-use-multi-threading-in-php-applications – Richard Housham Apr 05 '17 at 14:59
  • 1
    For the sake of some hypothetical `O(1)` you want to replace a single sort with `N` sorts. It is not an optimization, for sure. – axiac Apr 05 '17 at 14:59
  • At this time, I would like to say no, With php i think that can be done upto O(n). But need to research and while researching why dont you try JAVA, there are some libraries for Python too. And if you get any solution please post here, for reference. – BetaDev Apr 05 '17 at 14:59
  • Answer to the topic only _PHP sorting array on insert_ you can use SPL http://php.net/manual/en/class.splmaxheap.php or http://php.net/manual/en/class.splminheap.php Overview http://php.net/manual/en/spl.datastructures.php – JustOnUnderMillions Apr 05 '17 at 15:04
  • Maybe it is even better to aggregate everything into a new/temp table in your database and then let it sort. – Daniel W. Apr 05 '17 at 15:06

1 Answers1

0

The data structure you are looking for is a binary tree, where the left child is smaller than the parent and the right child is greater than the parent. Then a simple in-order traversal would give you the sorted list at the end in O(n) time, which is optimal. (Or O(1) per element.)

You do NOT want a min-heap because every time the minimum is retrieved from the heap, you need to spend O(log(n)) time before you can retrieve the next minimum item, which results in the total time of O(nlog(n)), which you are trying to avoid.

The difficulty in using binary trees come from having to ensure that the tree remains balanced. Otherwise the worst case time complexity is O(n) for each insertion. O(log(n)) worse case time algorithm is known for keeping the tree balanced after each insertion, but is not the simplest algorithm to implement. I've done a quick Google search and there seems to be already existing Binary Tree implementations in PHP.

This is the general idea behind what is known as Tree sort.

wookie919
  • 3,054
  • 24
  • 32