AgentSkillsCN

numpy-sorting

排序和搜索算法，包括 O(n) 分区、二分搜索和层次多键排序。触发条件：排序、argsort、分区、searchsorted、lexsort、nan 排序顺序。

SKILL.md
--- frontmatter
name: numpy-sorting
description: Sorting and searching algorithms including O(n) partitioning, binary search, and hierarchical multi-key sorting. Triggers: sort, argsort, partition, searchsorted, lexsort, nan sort order.

Overview

NumPy sorting provides efficient tools for ordering data. Beyond basic sorting, it includes partitioning for top-k selection and vectorized binary search for finding insertion points in sorted data.

When to Use

  • •Finding the top $k$ largest or smallest elements without a full sort ($O(N)$).
  • •Ordering data based on multiple criteria (e.g., sort by Date, then by Price).
  • •Mapping data into bins or ranges using binary search.
  • •Handling datasets containing NaNs where sorting order is sensitive.

Decision Tree

  1. •Need the indices of the sorted order (not the values)?
    • •Use np.argsort.
  2. •Only need the $k$ smallest elements?
    • •Use np.partition(arr, k). Elements to the left of index $k$ are smaller.
  3. •Finding where to insert a value to keep order?
    • •Use np.searchsorted(sorted_arr, value).

Workflows

  1. •

    Efficiently Finding the Smallest K Elements

    • •Identify an unsorted array.
    • •Call np.partition(arr, kth=k).
    • •Select the first k elements: result[:k].
  2. •

    Vectorized Lookup in Sorted Ranges

    • •Ensure the target array 'A' is sorted.
    • •Pass a list of values 'V' to np.searchsorted(A, V).
    • •Use the returned indices to map values to specific bins or ranges.
  3. •

    Indirect Multi-Key Sort

    • •Define primary and secondary key arrays.
    • •Use np.lexsort((secondary, primary)) to get the index array.
    • •Apply the indices to the data to achieve the desired hierarchical sort order.

Non-Obvious Insights

  • •NaN Position: np.nan is treated as larger than np.inf and is always sorted to the end of the array.
  • •Partition Performance: Partitioning along the last axis is significantly faster and uses less memory than partitioning along any other axis.
  • •Lexsort Order: lexsort takes keys in reverse order of importance; the last key in the sequence is the primary sort key.

Evidence

  • •"In the output array, all elements smaller than the k-th element are located to the left of this element and all equal or greater are located to its right." Source
  • •"Binary search is used to find the required insertion points." Source

Scripts

  • •scripts/numpy-sorting_tool.py: Implements top-k selection and hierarchical lexsort.
  • •scripts/numpy-sorting_tool.js: Basic sort simulation.

Dependencies

  • •numpy (Python)

References