The problem is interesting enough. However, I fear that it attracts solutions that are over-complex, and the solution in the question seems to be complex.

Other granular issues -

You're tracking calls to Arrays.sort, when it would be more interesting to track comparison calls.

int offsets[] is C-style array syntax; you should convert to Java syntax.

candidates = (E[][]) new Object[t][]; suffers from the usual Java generic problem of type erasure. This Object type leaks to your output and causes grief. You should choose one of the several type-strong ways around this problem.

Alternative

Trusting that the implementation of PriorityQueue is itself efficient (it's based on a priority heap), this can be as simple as

public class TopByOrder<E> { public final int t; public final Comparator<E> comparator; public TopByOrder(int t, Comparator<E> comparator) { this.t = t; this.comparator = comparator; } public PriorityQueue<E> reduce(Collection<E> in) { PriorityQueue<E> out = new PriorityQueue<>(t + 1, comparator); for (E entry: in) { out.add(entry); while (out.size() > t) out.remove(); } return out; } 

with demo code

 public static class CountingComparator implements Comparator<String> { private int ncalls = 0; @Override public int compare(String o1, String o2) { ++ncalls; return o1.compareTo(o2); } public int getNcalls() { return ncalls; } } public static void main(String[] args) { CountingComparator comparator = new CountingComparator(); TopByOrder<String> topper = new TopByOrder<>(3, comparator); List<String> in = List.of( "for", "int", "offset", "n", "k", "order", "apply", "many", "runnersUp", "top", "candidates", "offsets", "trickle", "down", "x", "z" ); for (String out: topper.reduce(in)) { System.out.println(out); } System.out.printf("Calls: %d%n", comparator.getNcalls()); } } 

(a parallel Stream collector is also possible.)

With all of your sample inputs included, this costs 47 comparator calls. I cannot currently compare this result to your own code, since that seems to have a casting problem; but until performance becomes an overriding concern I would prefer the simpler solution.

As previously explained, I found the OP code to be not quite transparently obvious. It wasn't clear to me why there needed to be so many abstractions between the problem statement and the implemented solution.

Here is my proposed solution.

def find_top_t(t: int, a: np.ndarray, k: int = K) -> np.ndarray: ... if len(a) <= t: sort_k(a, 0, t) while len(a) > t: for i in range(0, len(a), k): sort_k(a, i, k) a[i + t : i + k] = tombstone # ... a = np.array(list(filter(lambda x: x != tombstone, a))) return a[:t] 

I count about eight SLOC. I don't understand why we might need significantly more than that.

(Assume tombstone is a manifest constant, chosen to be outside the range of interest for the application.)

In the interest of completeness, here is a full implementation along with a test suite that exercises it.

# based on https://codereview.stackexchange.com/questions/287745/determine-top-t-values # cf https://stackoverflow.com/questions/52713266/most-efficient-way-to-get-the-largest-3-elements-of-an-array-using-no-comparison from collections import Counter from contextlib import contextmanager from functools import partial from random import shuffle import unittest from beartype import beartype from hypothesis import given from hypothesis import strategies as st import numpy as np cnt: Counter = Counter() # an event counter @contextmanager def count_sort_calls(): cnt["sort"] = 0 yield cnt @beartype def roll_some_numbers(n: int = 1000) -> np.ndarray[int, np.dtype[np.int_]]: """Produces N distinct random integers that are conveniently small.""" # Leaving room between entries deals with pigeonhole principle & birthday paradox. big_n = int(1.5 * n) a = np.random.randint(0, big_n, 2 * big_n) a = np.array(sorted(set(a.tolist()))[:n]) assert len(a) == n return a K = 5 @beartype def sort_k(a: np.ndarray, start: int, k: int) -> None: """Puts K elements into descending order.""" # The "top" elements will appear at the front. # This is convenient for truncated displays of large arrays. assert 0 <= start < len(a) cnt["sort"] += 1 a[start : start + k] = sorted(a[start : start + k], reverse=True) @beartype def find_top_t(t: int, a: np.ndarray, k: int = K) -> np.ndarray: assert t < K assert t <= len(a) tombstone = a.min() - 1 # sentinel value assert tombstone not in a # true by construction if len(a) <= t: sort_k(a, 0, t) while len(a) > t: for i in range(0, len(a), k): sort_k(a, i, k) a[i + t : i + k] = tombstone # Now coalesce the survivors, shrinking the array of candidate answer values. a = np.array(list(filter(lambda x: x != tombstone, a))) return a[:t] T = 3 _moderately_large = 2**63 - 1 # The set of all integers is very, very large, # and cPython can model a pretty big subset of them. # Let's restrict the ambitions of `hypothosis` to something more reasonable. _small_integers = partial( st.integers, min_value=-_moderately_large, max_value=_moderately_large, ) def shuffled(a: list[int]) -> list[int]: b = a.copy() shuffle(b) return b @beartype class TestTopT(unittest.TestCase): """Verifies that the Right Thing happens, in less than a second.""" def test_roll(self) -> None: a = roll_some_numbers() self.assertLess(a[0], a[-1]) def test_sorted_slice(self) -> None: a = np.array(range(8)) sort_k(a, 2, k=3) self.assertEqual([0, 1, 4, 3, 2, 5, 6, 7], a.tolist()) sort_k(a, 2, K) self.assertEqual([0, 1, 6, 5, 4, 3, 2, 7], a.tolist()) a.sort() sort_k(a, 6, K) # Partial sort, at end of array, works as expected. self.assertEqual([0, 1, 2, 3, 4, 5, 7, 6], a.tolist()) def test_top_t(self, t=T) -> None: a = roll_some_numbers(10) with count_sort_calls() as cnt: xs = find_top_t(t, a.copy()).tolist() self.assertEqual(5, cnt["sort"]) self.assertEqual(xs, sorted(xs, reverse=True)) self.assertEqual(xs, sorted(a, reverse=True)[:t]) def test_with_dups(self, t=T, n=10_000) -> None: a = np.random.randint(0, n // 2, n) self.assertLess(len(set(a)), len(a) / 2) xs = find_top_t(t, a.copy()).tolist() self.assertEqual(xs, sorted(xs, reverse=True)) self.assertEqual(xs, sorted(a, reverse=True)[:t]) def test_imbalanced(self, t=T, num_distractors=10_000) -> None: with count_sort_calls() as cnt: a = np.array(shuffled([1] * t + [0] * num_distractors)) self.assertEqual([1] * t, find_top_t(t, a).tolist()) self.assertEqual(num_distractors / 2 + 12, cnt["sort"]) with count_sort_calls() as cnt: a = np.array(shuffled([1] * (t - 1) + [0] * num_distractors)) self.assertEqual([1] * (t - 1) + [0], find_top_t(t, a).tolist()) self.assertEqual(num_distractors / 2 + 12, cnt["sort"]) def test_010(self) -> None: a = np.array([0, 1, 0]) # This input vector was surfaced by hypothesis. self.assertEqual([1, 0, 0], find_top_t(T, a).tolist()) @given(st.lists(_small_integers(), min_size=T, max_size=100)) def test_with_hypothesis(self, lst: list[int]) -> None: a = np.array(lst) xs = find_top_t(T, a.copy()).tolist() self.assertEqual(xs, sorted(xs, reverse=True)) self.assertEqual(xs, sorted(a, reverse=True)[:T]) 

EDIT

@greybeard, here is my current pip setup:

$ pip freeze absl-py==2.0.0 aiohttp==3.9.1 aiosignal==1.3.1 alembic==1.13.1 altair==5.2.0 annotated-types==0.6.0 argon2-cffi==23.1.0 argon2-cffi-bindings==21.2.0 astroid==3.0.1 asttokens==2.4.1 atomicwrites==1.4.1 attrs==23.1.0 beartype==0.16.4 beautifulsoup4==4.12.2 bitarray==2.8.3 black==23.11.0 blinker==1.7.0 blis==0.7.11 boltons==23.1.1 branca==0.7.0 Brotli @ file:///Users/runner/miniforge3/conda-bld/brotli-split_1695989838345/work cachetools==5.3.2 catalogue==2.0.10 certifi @ file:///home/conda/feedstock_root/build_artifacts/certifi_1700303426725/work/certifi cffi==1.16.0 charset-normalizer @ file:///home/conda/feedstock_root/build_artifacts/charset-normalizer_1698833585322/work click==8.1.7 click-plugins==1.1.1 cligj==0.7.2 cloudpathlib==0.16.0 cloudpickle==3.0.0 colorlog==6.8.0 comm==0.2.0 compact-json==1.6.1 confection==0.1.4 contourpy==1.2.0 coverage==5.5 cycler==0.12.1 cymem==2.0.8 Cython @ file:///Users/runner/miniforge3/conda-bld/cython_1701025484377/work dacite==1.8.1 dask==2023.11.0 datasets==2.15.0 decorator==5.1.1 deprecation==2.1.0 dill==0.3.7 en-core-web-sm @ https://github.com/explosion/spacy-models/releases/download/en_core_web_sm-3.7.1/en_core_web_sm-3.7.1-py3-none-any.whl#sha256=86cc141f63942d4b2c5fcee06630fd6f904788d2f0ab005cce45aadb8fb73889 et-xmlfile==1.1.0 evaluate==0.4.1 executing==2.0.1 eyed3==0.9.7 face==20.1.1 fasteners==0.19 filelock @ file:///home/conda/feedstock_root/build_artifacts/filelock_1698714947081/work filetype==1.2.0 fiona==1.9.5 flake8==6.1.0 Flask==3.0.0 fonttools==4.45.1 frozenlist==1.4.0 fsspec @ file:///home/conda/feedstock_root/build_artifacts/fsspec_1697919321618/work fuzzywuzzy==0.18.0 geographiclib==2.0 geopandas==0.14.1 geopy==2.4.1 gitdb==4.0.11 GitPython==3.1.40 glom==23.5.0 gmpy2 @ file:///Users/runner/miniforge3/conda-bld/gmpy2_1666808689326/work gpxpy==1.6.2 greenlet==3.0.1 haversine==2.8.0 html2text==2020.1.16 htmlmin==0.1.12 huggingface-hub==0.19.4 hypothesis==6.91.0 idna @ file:///home/conda/feedstock_root/build_artifacts/idna_1701026962277/work ImageHash==4.3.1 imbalanced-learn==0.11.0 importlib-metadata==6.8.0 iniconfig==2.0.0 ipyleaflet==0.18.0 ipython==8.18.1 ipywidgets==8.1.1 isort==5.12.0 itsdangerous==2.1.2 jedi==0.19.1 Jinja2 @ file:///home/conda/feedstock_root/build_artifacts/jinja2_1654302431367/work joblib @ file:///home/conda/feedstock_root/build_artifacts/joblib_1691577114857/work jsonschema==4.20.0 jsonschema-specifications==2023.11.1 jupyterlab-widgets==3.0.9 kiwisolver==1.4.5 langcodes==3.3.0 Levenshtein==0.23.0 liac-arff==2.5.0 llvmlite==0.41.1 locket==1.0.0 lxml==4.9.3 Mako==1.3.0 markdown-it-py==3.0.0 markdownify==0.11.6 MarkupSafe @ file:///Users/runner/miniforge3/conda-bld/markupsafe_1695367621021/work matplotlib==3.7.3 matplotlib-inline==0.1.6 maturin==1.3.2 mccabe==0.7.0 mdurl==0.1.2 memory-profiler==0.61.0 minio==7.2.0 mpmath @ file:///home/conda/feedstock_root/build_artifacts/mpmath_1678228039184/work multidict==6.0.4 multimethod==1.10 multiprocess==0.70.15 murmurhash==1.0.10 mypy==1.7.1 mypy-extensions==1.0.0 netifaces==0.11.0 networkit==10.1 networkx @ file:///home/conda/feedstock_root/build_artifacts/networkx_1698504735452/work nltk==3.8.1 numba==0.58.1 numbers-parser==4.4.6 numpy==1.25.2 onnx==1.15.0 opencv-python==4.8.1 openml==0.14.1 openpyxl==3.1.2 optuna==3.5.0 osmnx==1.7.1 packaging==23.2 palettable==3.3.3 pandas==2.0.3 parso==0.8.3 partd==1.4.1 pathlib-mate==1.2.1 pathspec==0.11.2 patsy==0.5.3 pendulum==2.1.2 pexpect==4.9.0 phik==0.12.3 Pillow @ file:///Users/runner/miniforge3/conda-bld/pillow_1697423658740/work platformdirs==4.0.0 pluggy==1.3.0 polars==0.19.18 preshed==3.0.9 prettytable==3.9.0 prompt-toolkit==3.0.41 protobuf==4.25.1 psutil==5.9.6 ptyprocess==0.7.0 pure-eval==0.2.2 py4j==0.10.9.7 pyarrow==14.0.1 pyarrow-hotfix==0.6 pyAudioAnalysis==0.3.14 pycodestyle==2.11.1 pycparser==2.21 pycryptodome==3.19.0 pydantic==2.5.2 pydantic_core==2.14.5 pydeck==0.8.0 pydub==0.25.1 pyflakes==3.1.0 pygame==2.5.2 Pygments==2.17.2 pylint==3.0.2 pynisher==1.0.10 pyo3-pack==0.6.1 pyparsing==3.1.1 pyproj==3.6.1 PySocks @ file:///home/conda/feedstock_root/build_artifacts/pysocks_1661604839144/work pyspark==3.5.0 pytest==7.4.3 pytest-cov==4.1.0 python-dateutil==2.8.2 python-Levenshtein==0.23.0 python-snappy==0.6.1 pytz==2023.3.post1 pytzdata==2020.1 PyWavelets==1.5.0 PyYAML==6.0.1 rapidfuzz==3.5.2 referencing==0.31.0 regex==2022.10.31 requests @ file:///home/conda/feedstock_root/build_artifacts/requests_1684774241324/work responses==0.18.0 rich==13.7.0 roman==3.3 rouge-score==0.1.2 rpds-py==0.13.1 ruamel.yaml==0.18.5 ruamel.yaml.clib==0.2.8 ruff==0.1.6 safetensors==0.4.1 scikit-learn @ file:///Users/runner/miniforge3/conda-bld/scikit-learn_1698225196710/work SciPy @ file:///Users/runner/miniforge3/conda-bld/scipy-split_1700812582578/work/dist/scipy-1.11.4-cp311-cp311-macosx_10_9_x86_64.whl#sha256=5b875a53aeeb67c8451f09cb04406bae2b2ac7255cf4b820ae8098cfc1031194 seaborn==0.12.2 sentencepiece==0.1.99 shapely==2.0.2 sigfig==1.3.3 six==1.16.0 smart-open==6.4.0 smmap==5.0.1 sortedcontainers==2.4.0 soupsieve==2.5 spacy==3.7.2 spacy-legacy==3.0.12 spacy-loggers==1.0.5 SQLAlchemy==1.4.50 sqlalchemy-mate==1.4.28.4 srsly==2.4.8 stack-data==0.6.3 statsmodels==0.14.0 streamlit==1.28.2 streamlit-image-coordinates==0.1.6 sympy @ file:///home/conda/feedstock_root/build_artifacts/sympy_1684180540116/work tabulate==0.9.0 tangled-up-in-unicode==0.2.0 tenacity==8.2.3 thinc==8.2.1 threadpoolctl @ file:///home/conda/feedstock_root/build_artifacts/threadpoolctl_1689261241048/work tokenize-rt==5.2.0 tokenizers==0.15.0 toml==0.10.2 tomlkit==0.12.3 toolz==0.12.0 torch @ file:///Users/runner/miniforge3/conda-bld/pytorch-recipe_1699313596155/work torchvision @ file:///Users/runner/miniforge3/conda-bld/torchvision-split_1701228065651/work tornado==6.4 tqdm==4.66.1 traitlets==5.14.0 traittypes==0.2.1 transformers==4.35.2 typeguard==4.1.5 typer==0.9.0 types-requests==2.31.0.10 typing_extensions @ file:///home/conda/feedstock_root/build_artifacts/typing_extensions_1695040754690/work tzdata==2023.3 tzlocal==5.2 Unidecode==1.3.7 urllib3 @ file:///home/conda/feedstock_root/build_artifacts/urllib3_1699933488691/work uszipcode==1.0.1 validators==0.22.0 visions==0.7.5 wasabi==1.1.2 watchdog==3.0.0 wcwidth==0.2.12 weasel==0.3.4 Werkzeug==3.0.1 widgetsnbextension==4.0.9 wordcloud==1.9.2 xgboost==1.7.6 xlsx2csv==0.8.1 xmltodict==0.13.0 xxhash==3.4.1 xyzservices==2023.10.1 yarl==1.9.3 ydata-profiling==4.6.2 zipp==3.17.0 

It came from this:

$ cat environment.yml && conda env update name: problems channels: - conda-forge dependencies: - cython >= 0.29.34 - pip >= 23.3.1 - py-opencv >= 4.6.0 - py-xgboost >= 1.7.1 - python >= 3.11.4 - torchvision >= 0.16.1 - pip: - beartype >= 0.16.4 - beautifulsoup4 >= 4.12.2 - bitarray >= 2.8.3 - black[jupyter] >= 23.11.0 - dask >= 2023.11.0 - datasets >= 2.15.0 - evaluate >= 0.4.1 - eyed3 >= 0.9.7 - fasteners >= 0.19 - flake8 >= 6.1.0 - flask >= 2.3.2 - geopandas >= 0.14.1 - geopy >= 2.4.1 - glom >= 23.5.0 - gpxpy >= 1.6.2 - html2text >= 2020.1.16 - huggingface_hub >= 0.16.4 - hypothesis >= 6.91.0 - imbalanced-learn >= 0.11.0 - ipyleaflet >= 0.18.0 - isort >= 5.12.0 - lxml >= 4.9.3 - markdownify >= 0.11.6 - matplotlib >= 3.7.3 - maturin >= 1.3.2 - memory-profiler >= 0.61.0 - mypy >= 1.7.1 - netifaces >= 0.11.0 - networkit >= 10.1 - numba >= 0.58.1 - numbers_parser >= 3.11.0 - numpy >= 1.25.2 - onnx >= 1.15.0 - openml >= 0.14.1 - openpyxl >= 3.1.2 - osmnx >= 1.7.1 - palettable >= 3.3.3 - pandas >= 2.0.3 - pillow >= 9.5.0 - polars >= 0.19.18 - psutil >= 5.9.6 - pyarrow >= 14.0.1 - pyaudioanalysis >= 0.3.14 - pydeck >= 0.8.0 - pydub >= 0.25.1 - pygame >= 2.5.2 - pylint >= 3.0.2 - pynisher >= 1.0.10 - pyo3-pack >= 0.6.1 - pyspark >= 3.5.0 - pytest >= 7.4.3 - pytest-cov >= 4.1.0 - python-Levenshtein >= 0.23.0 - pywavelets >= 1.4.1 - roman >= 3.3 - rouge_score >= 0.1.2 - ruamel.yaml >= 0.18.5 - ruff >= 0.1.6 - scikit-learn >= 1.3.2 - scipy >= 1.11.3 - sentencepiece >= 0.1.99 - spacy >= 3.7.2 - sqlalchemy >= 1.4.47, < 2 - streamlit >= 1.28.2 - streamlit-image-coordinates >= 0.1.6 - tabulate >= 0.9.0 - transformers >= 4.35.2 - typer >= 0.9.0 - types-requests >= 2.31.0.10 - unidecode >= 1.3.6 - uszipcode >= 1.0.1 - watchdog >= 3.0.0 - xlsx2csv >= 0.8.1 - ydata-profiling >= 4.6.2 ... 

Almost certainly, nearly every one of those packages is irrelevant.

I bet that beartype was the one you got caught up on.

It is an abstract logic puzzle.

When you have a function ordering 5 elements, and search the 3 highest elements, a naive solution would be:

1. start with index 0
2. order the next 5 elements from index
3. the last 3 elements of that sub-array are the current highest
4. skip the lowest 2 elements by increasing the index by 2
5. repeat till end
6. mind the number of elements

There might be a smarter solution by ordering first at indices 0, 5, 10, ... and then shoving elements together for yet another sequence of orderings.

• The naive solution above for N elements needs to call the order function N/2 times.
• The second idea would in the first sequence (partial result) need N/5 order calls, yielding a new array of N*3/5 elements, for which you could do a recursive call. The total number of calls is mathematically interesting.

My guess is, that the original question was intended to ponder about such optimization ideas, whereas you dove immediately into implementation issues.

By the way premature jumping into implementation is a professional risk.

After comment some feedback

I guess @greybeard wants some concrete code, especially on variants (?). Because stylistically the original code shows non-java background, here a rework.

The algorithm is done in determineTop (N/2 steps) and I made a variant with determineTop2 where the many do-while loops add some steps.

The code in-situ (in-place) moves sub-arrays, hence for determineTop2 it was needed to pass the array size.

public class PickTopByOrdering<T extends Comparable<T>> { public final int topSize; public final int orderSize; public int calls; public PickTopByOrdering(int topSize, int orderSize) { this.topSize = topSize; this.orderSize = orderSize; } /** * Order at the given offset orderSize elements before length. * @param array of all values. * @param length of the array considered. * @param offset index to start with. * @return the next offset after what was sorted. */ private int order(T[] array, int length, int offset) { int end = Math.min(offset + orderSize, length); Arrays.sort(array, offset, end); return end; } private T[] determineTop(T[] array, int length) { calls = 0; for (int i = 0; i < length; i += orderSize - topSize) { order(array, length, i); ++calls; } int start = Math.max(0, length - topSize); T[] top = Arrays.copyOfRange(array, start, length); return top; } private T[] determineTop2(T[] arrays, int length) { calls = 0; do { int nextLength = 0; for (int i = 0; i < length; ) { int nextI = order(arrays, length, i); ++calls; int topI = Math.max(i, nextI - topSize); int moved = Math.min(topSize, nextI - i); System.arraycopy(arrays, topI, arrays, nextLength, moved); nextLength += moved; i = nextI; } System.out.printf("... %d -> %d, calls: %d%n", length, nextLength, calls); length = nextLength; } while (length > topSize); int start = Math.max(0, length - topSize); T[] top = Arrays.copyOfRange(arrays, start, length); return top; } public static void main(String[] args) { PickTopByOrdering<String> topper = new PickTopByOrdering<>(3, 5); String[] arrays = { "for", "int", "offset", "n", "k", "order", "apply", "many", "runnersUp", "top", "candidates", "this", "example", "creates", "an", "instance", "which", "is", "intended", "to", "display", "objects", "y", "offsets", "trickle", "down", "x", "z" }; String[] top = topper.determineTop2(arrays, arrays.length); System.out.println(Arrays.toString(top)); System.out.printf("%d array element; %d calls.%n", arrays.length, topper.calls); } } 

Now you might consider determineTop2 no win, especially with the System.arraycopy, but for other cases than 3, 5 say 3, 10 it might become interesting.

As said the code is just an attempt at stylistic improving all. And I am not sure this code indeed looks better.