Skip to main content

Efficient Market Ranking with QuickSelect Algorithm

· 2 min read
Max Kaido
Max Kaido
Architect

In the latest update to Mercury Bot (v0.126.0), we've introduced a significant improvement to our market ranking system using the QuickSelect algorithm. This optimization reduces the number of comparisons needed to find the top K markets, making our analysis more efficient and responsive.

The Challenge​

Our previous implementation compared every market with every other market to establish rankings. With N markets, this resulted in O(N²) comparisons. For 100 markets, we needed up to 4,950 comparisons! This was:

  • Time-consuming
  • Resource-intensive
  • Expensive in terms of API calls

Enter QuickSelect​

QuickSelect is a selection algorithm that finds the k-th smallest (or largest) element in an unordered list. Its average time complexity is O(N), meaning we can find our top K markets with far fewer comparisons.

How It Works​

  1. State Management: The algorithm maintains a state machine with four phases:

    • INIT: Sets up the partition
    • PARTITION: Compares markets against a pivot
    • RECURSE: Narrows down the search range
    • COMPLETE: Finalizes rankings

  2. Partitioning:

    currentPartition: {
      pivot: string;     // Reference market
      better: string[]; // Markets ranked lower
      worse: string[];  // Markets ranked higher
      equal: string[];   // Markets of equal strength
    }

  3. Confidence Tracking:

    confidence: {
      market: string;
      totalConfidence: number;
      comparisonCount: number;
      averageConfidence: number;
      lowestConfidence: number;
      highestConfidence: number;
      recentTrend: number;
    }

Key Benefits​

  1. Efficiency: Reduces comparisons from O(N²) to O(N)
  2. Incremental Progress: State machine allows pausing/resuming
  3. Confidence Metrics: Tracks reliability of rankings
  4. Error Handling: Gracefully handles failed comparisons

Real-world Impact​

For a typical set of 100 markets:

  • Old System: ~5,000 comparisons
  • New System: ~200 comparisons
  • 96% reduction in required comparisons!

Implementation Details​

The core of the algorithm is the partition step:

private async continuePartition(state: QuickSelectState): Promise<QuickSelectState> {
  // Compare current market with pivot
  const comparison = await this.compareMarkets(
    currentPartition.pivot,
    currentMarket,
    state.config
  );

  // Update partitions based on comparison
  if (comparison.winner === market) {
    // Market is stronger than pivot
    worse.push(market);
  } else if (comparison.winner === pivot) {
    // Market is weaker than pivot
    better.push(market);
  } else {
    // Markets are equal
    equal.push(market);
  }
}

Future Improvements​

  1. Dynamic pivot selection based on historical data
  2. Parallel comparisons for independent market pairs
  3. Machine learning to predict likely outcomes

Conclusion​

The QuickSelect implementation represents a major step forward in our market analysis capabilities. By dramatically reducing the number of required comparisons, we can provide faster, more efficient market rankings while maintaining high confidence in our results.

Stay tuned for more optimizations and improvements to Mercury Bot's market analysis capabilities!