Skip to content

Commit d01d598

Browse files
aocsalidavidm
authored andcommitted
ARROW-14003: [C++][Python] Not providing a sort_key in the "select_k_unstable" kernel crashes
This is a minor fix for issue ARROW-14003. Moreover I added some function (topK/bottomK) specialization in arrow/compute.py. @jorisvandenbossche Closes #11164 from aocsa/aocsa/ARROW-14003 Authored-by: Alexander <[email protected]> Signed-off-by: David Li <[email protected]>
1 parent 0dd68c2 commit d01d598

3 files changed

Lines changed: 122 additions & 17 deletions

File tree

‎cpp/src/arrow/compute/kernels/vector_sort.cc‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2337,9 +2337,12 @@ class SelectKUnstableMetaFunction : public MetaFunction {
23372337
const FunctionOptions* options, ExecContext* ctx) const {
23382338
const SelectKOptions& select_k_options = static_cast<const SelectKOptions&>(*options);
23392339
if (select_k_options.k < 0) {
2340-
return Status::Invalid("SelectK requires a nonnegative `k`, got ",
2340+
return Status::Invalid("select_k_unstable requires a nonnegative `k`, got ",
23412341
select_k_options.k);
23422342
}
2343+
if (select_k_options.sort_keys.size() == 0) {
2344+
return Status::Invalid("select_k_unstable requires a non-empty `sort_keys`");
2345+
}
23432346
switch (args[0].kind()) {
23442347
case Datum::ARRAY: {
23452348
return SelectKth(*args[0].make_array(), select_k_options, ctx);

‎python/pyarrow/compute.py‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -643,3 +643,85 @@ def fill_null(values, fill_value):
643643
fill_value = pa.scalar(fill_value.as_py(), type=values.type)
644644

645645
return call_function("coalesce", [values, fill_value])
646+
647+
648+
def top_k_unstable(values, k, sort_keys=None, memory_pool=None):
649+
"""
650+
Select the indices of the top-k ordered elements from array- or table-like
651+
data.
652+
653+
This is a specialization for :func:`select_k_unstable`. Output is not
654+
guaranteed to be stable.
655+
656+
Parameters
657+
----------
658+
values : Array, ChunkedArray, RecordBatch, or Table
659+
k : The number of `k` elements to keep.
660+
sort_keys : Column key names to order by when input is table-like data.
661+
662+
Returns
663+
-------
664+
result : Array of indices
665+
666+
Examples
667+
--------
668+
>>> import pyarrow as pa
669+
>>> import pyarrow.compute as pc
670+
>>> arr = pa.array(["a", "b", "c", None, "e", "f"])
671+
>>> pc.top_k_unstable(arr, k=3)
672+
<pyarrow.lib.UInt64Array object at 0x7fdcb19d7f30>
673+
[
674+
5,
675+
4,
676+
2
677+
]
678+
"""
679+
if sort_keys is None:
680+
sort_keys = []
681+
if isinstance(values, (pa.Array, pa.ChunkedArray)):
682+
sort_keys.append(("dummy", "descending"))
683+
else:
684+
sort_keys = map(lambda key_name: (key_name, "descending"), sort_keys)
685+
options = SelectKOptions(k=k, sort_keys=sort_keys)
686+
return call_function("select_k_unstable", [values], options, memory_pool)
687+
688+
689+
def bottom_k_unstable(values, k, sort_keys=None, memory_pool=None):
690+
"""
691+
Select the indices of the bottom-k ordered elements from
692+
array- or table-like data.
693+
694+
This is a specialization for :func:`select_k_unstable`. Output is not
695+
guaranteed to be stable.
696+
697+
Parameters
698+
----------
699+
values : Array, ChunkedArray, RecordBatch, or Table
700+
k : The number of `k` elements to keep.
701+
sort_keys : Column key names to order by when input is table-like data.
702+
703+
Returns
704+
-------
705+
result : Array of indices
706+
707+
Examples
708+
--------
709+
>>> import pyarrow as pa
710+
>>> import pyarrow.compute as pc
711+
>>> arr = pa.array(["a", "b", "c", None, "e", "f"])
712+
>>> pc.bottom_k_unstable(arr, k=3)
713+
<pyarrow.lib.UInt64Array object at 0x7fdcb19d7fa0>
714+
[
715+
0,
716+
1,
717+
2
718+
]
719+
"""
720+
if sort_keys is None:
721+
sort_keys = []
722+
if isinstance(values, (pa.Array, pa.ChunkedArray)):
723+
sort_keys.append(("dummy", "ascending"))
724+
else:
725+
sort_keys = map(lambda key_name: (key_name, "ascending"), sort_keys)
726+
options = SelectKOptions(k=k, sort_keys=sort_keys)
727+
return call_function("select_k_unstable", [values], options, memory_pool)

‎python/pyarrow/tests/test_compute.py‎

Lines changed: 36 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1859,35 +1859,42 @@ def validate_select_k(select_k_indices, arr, order, stable_sort=False):
18591859
assert actual == expected
18601860

18611861
arr = pa.array([1, 2, None, 0])
1862-
for order in ["descending", "ascending"]:
1863-
for k in [0, 2, 4]:
1862+
for k in [0, 2, 4]:
1863+
for order in ["descending", "ascending"]:
18641864
result = pc.select_k_unstable(
18651865
arr, k=k, sort_keys=[("dummy", order)])
18661866
validate_select_k(result, arr, order)
18671867

1868-
result = pc.select_k_unstable(arr, options=pc.SelectKOptions(
1869-
k=2, sort_keys=[("dummy", "descending")]))
1868+
result = pc.top_k_unstable(arr, k=k)
1869+
validate_select_k(result, arr, "descending")
1870+
1871+
result = pc.bottom_k_unstable(arr, k=k)
1872+
validate_select_k(result, arr, "ascending")
1873+
1874+
result = pc.select_k_unstable(
1875+
arr, options=pc.SelectKOptions(
1876+
k=2, sort_keys=[("dummy", "descending")])
1877+
)
18701878
validate_select_k(result, arr, "descending")
18711879

1872-
result = pc.select_k_unstable(arr, options=pc.SelectKOptions(
1873-
k=2, sort_keys=[("dummy", "ascending")]))
1880+
result = pc.select_k_unstable(
1881+
arr, options=pc.SelectKOptions(k=2, sort_keys=[("dummy", "ascending")])
1882+
)
18741883
validate_select_k(result, arr, "ascending")
18751884

18761885

18771886
def test_select_k_table():
1878-
table = pa.table({"a": [1, 2, 0], "b": [1, 0, 1]})
1879-
1880-
def validate_select_k(select_k_indices, table, sort_keys,
1881-
stable_sort=False):
1882-
sorted_indices = pc.sort_indices(table, sort_keys=sort_keys)
1887+
def validate_select_k(select_k_indices, tbl, sort_keys, stable_sort=False):
1888+
sorted_indices = pc.sort_indices(tbl, sort_keys=sort_keys)
18831889
head_k_indices = sorted_indices.slice(0, len(select_k_indices))
18841890
if stable_sort:
18851891
assert select_k_indices == head_k_indices
18861892
else:
1887-
expected = pc.take(table, head_k_indices)
1888-
actual = pc.take(table, select_k_indices)
1893+
expected = pc.take(tbl, head_k_indices)
1894+
actual = pc.take(tbl, select_k_indices)
18891895
assert actual == expected
18901896

1897+
table = pa.table({"a": [1, 2, 0], "b": [1, 0, 1]})
18911898
for k in [0, 2, 4]:
18921899
result = pc.select_k_unstable(
18931900
table, k=k, sort_keys=[("a", "ascending")])
@@ -1896,13 +1903,26 @@ def validate_select_k(select_k_indices, table, sort_keys,
18961903
result = pc.select_k_unstable(
18971904
table, k=k, sort_keys=[("a", "ascending"), ("b", "ascending")]
18981905
)
1899-
validate_select_k(result, table, sort_keys=[
1900-
("a", "ascending"), ("b", "ascending")])
1906+
validate_select_k(
1907+
result, table, sort_keys=[("a", "ascending"), ("b", "ascending")]
1908+
)
1909+
1910+
result = pc.top_k_unstable(table, k=k, sort_keys=["a"])
1911+
validate_select_k(result, table, sort_keys=[("a", "descending")])
1912+
1913+
result = pc.bottom_k_unstable(table, k=k, sort_keys=["a", "b"])
1914+
validate_select_k(
1915+
result, table, sort_keys=[("a", "ascending"), ("b", "ascending")]
1916+
)
19011917

19021918
with pytest.raises(ValueError,
1903-
match="SelectK requires a nonnegative `k`"):
1919+
match="select_k_unstable requires a nonnegative `k`"):
19041920
pc.select_k_unstable(table)
19051921

1922+
with pytest.raises(ValueError, match="select_k_unstable requires "
1923+
"a non-empty `sort_keys`"):
1924+
pc.select_k_unstable(table, k=2)
1925+
19061926
with pytest.raises(ValueError, match="not a valid order"):
19071927
pc.select_k_unstable(table, k=k, sort_keys=[("a", "nonscending")])
19081928

0 commit comments

Comments
 (0)