4
\$\begingroup\$

I tried to write a decent answer to Most efficient way to get the largest 3 elements of an array using no comparisons but a procedure for ordering 5 elements descendantly.
I could not come up with something concise, let alone compelling.
I assumed duplicate values were allowed; unique values allowing "multidimensional trickery", code would probably end up more involved, still.

I coded around order() ordering non-descendingly; one thing nagging me is I might have been better off choosing non-ascendingly.

package net.reserves.human.coder.greybeard.sandbox;

import java.util.Arrays;

/** Determine top t values given a procedure to order k values. */
// currently for t < k; thinking k =(<) t gets (much) more complicated, still
public class TopByOrderK<E> {
    /** <code>apply(values, first, count)</code>
     *  orders <code>count</code> values in <code>E [] values</code>
     *  from <code>first</code> non-descendingly. */
    public interface OrderK<E> {
        /** <code>apply(values, first, count)</code>
         *  orders <code>count</code> values in <code>E [] values</code>
         *  from <code>first</code> non-descendingly. */
        public default void apply(E[] values, int offset, int k) {
            Arrays.sort(values, offset, offset + k);
        }
    }

    public TopByOrderK(int top, int k, OrderK<E> order) {
        if (k <= top)
            throw new IllegalArgumentException("number of values"
                + " that can be ordered by a single call shall exceed"
                + " the number of top values to determine.");
        this.t = top;
        t_ = top -1;
        this.k = k;
        k_ = k - 1;
        k_t = k - top;
        this.order = null == order ? new OrderK<E>() {} : order;
    }
    OrderK<E> order;
    int calls;
    void orderK(E[] values, int offset) {
        calls += 1;
        order.apply(values, offset, k);
    }
    
    int offsets[], t, t_, k, k_, k_t;
    E[] candidates[];
    E nonTopT;
    
    /** From <code>valid</code> valid values
     *  in <code>candidates[--keep]</code>, distribute up to 
     *  <code>keep</code> values to this and "lower priority"
     *  <code>candidates</code> arrays */
    void keep(int keep, int valid) {
        final E values[] = candidates[--keep];
        orderK(values, 0);
        nonTopT = values[0];
        int down = k_ - keep;
        while (0 <= --keep && 0 < --valid) {
            candidates[keep][offsets[keep]]
                = values[down + keep];
            if (k <= (offsets[keep] += 1)) {
                if (0 < keep)
                    keep(keep, k);
                else {
                    orderK(candidates[0], 0);
                    candidates[0][0] = candidates[0][k_];
                }
                offsets[keep] = 1;
            }
        }
    }

    /** Determine top t values given a procedure to order k values. */
    // ToDo: define *determine*; currently: Leave in decreasing priority
    //                                            in candidates[t_]
    // currently for t < k; k =(<) t gets (much) more complicated, still
    // main idea: comparing values known to be smaller than t-1 values,
    // only one needs to be kept; <t-2: 2, ...
    // compare values of same "potential rank" up to some wrap-up.
    public void topByOrderK(final E[] many) {
        final int n = many.length;
        if (n < t)
            throw new IllegalArgumentException("number of values supplied"
                + " may not be less than number of result values required.");
        // keep up to k values of each potential rank ...
        candidates = (E[][]) new Object[t][];
                          // java.lang.reflect.
                          // Array.newInstance(many.getClass(), t);
        for (int ci = candidates.length ; 0 <= --ci ; )
            candidates[ci] = Arrays.copyOf(many, k);
        if (n <= k) {  // one application of orderK should suffice
            handleFew(many);
            return;
        }
        // ... and next free offset
        offsets = new int[t];
        
        candidates[t_][k_] = many[0];  // arraycopy in loop will fill 0:k_
        int offset = 1;                // used in wrap-up
        for ( ; offset <= n - k ; offset += k_) {
            System.arraycopy(many, offset, candidates[t_], 0, k_);
            keep(t, k);
        }
        for (int left = n - offset ; 0 < left ; left = 0) {
            candidates[t_][0] = candidates[t_][k_];
            System.arraycopy(many, offset, candidates[t_], 1, left);
            offsets[t_] = 1 + left;
        }
        for (int rank = t, top = Integer.MIN_VALUE ; 0 <= --rank ; ) {
            switch(offsets[rank]) {
            case 0: // shouldn't happen?!
                break;
            case 1:
                top = 0;
                break;
            default:
                Arrays.fill(candidates[rank], offsets[rank], k, nonTopT);
                keep(rank+1, offsets[rank]);
                top = k_;
            }
            candidates[t_][k_t+rank] = candidates[rank][top];
        }
//      orderK(candidates[t_], 0);  // ??
    }
    /** place top t of up to k values in candidates[t_][0:t] */
    private void handleFew(final E[] many) {
        final int n = many.length;
        if (n == t)
            return;
        if (n < k) {
            if (1 < t) {  // fill up k values to order
                Arrays.fill(candidates[0], n, k, many[0]);
                orderK(candidates[0], 0);
            }
            System.arraycopy(many, 0, candidates[0], k - n, n);
        }
        orderK(candidates[0], 0);
        for (int p = 0 ; p <= k/2 ; p++) {  // t_ might be 0
            E tmp = candidates[0][k-p];
            candidates[0][k-p] = candidates[t_][p]; 
            candidates[t_][p] = tmp;
        }
    }


    public static void main(String[] args) {
        TopByOrderK<String> topper = new TopByOrderK<>(3, 5, null);
        String many[] = {
                "for", "int", "offset", "n", "k", "order", "apply", "many",
//              "runnersUp", "top", "candidates",
//              "offsets", "trickle", "down", "x", "z"
            };
        topper.topByOrderK(many);
        System.out.println(Arrays.asList(topper.candidates[topper.t_])
            .subList(topper.k_t, topper.k));
        System.out.println(topper.calls + " calls");
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ class [[Ljava.lang.Object; cannot be cast to class [[Ljava.lang.String; ([[Ljava.lang.Object; and [[Ljava.lang.String; are in module java.base of loader 'bootstrap') ? \$\endgroup\$
    – Reinderien
    Dec 25, 2023 at 18:15
  • \$\begingroup\$ Sure. Otherwise: what motivates this above something very simple like an inner priority queue? It seems pretty complex. \$\endgroup\$
    – Reinderien
    Dec 25, 2023 at 18:47
  • \$\begingroup\$ @Reinderien Of course you can implement a priority queue, even (ab)using an orderK() as a comparison copying values appropriately. This will not get anywhere near few calls to order(). (If so inclined, you can view candidates as a capacity limited speciality priority queue.) \$\endgroup\$
    – greybeard
    Dec 26, 2023 at 7:35
  • \$\begingroup\$ (I still wonder whether or not this is about algorithm. Short of handling just k-t fresh values in each iteration, sure this is the most simple approach…) \$\endgroup\$
    – greybeard
    Dec 28, 2023 at 7:26
  • \$\begingroup\$ The edit seems like answer invalidation. Should I be worried? \$\endgroup\$
    – Reinderien
    Dec 28, 2023 at 14:49

4 Answers 4

2
\$\begingroup\$
    ... non-descendingly. */

I prefer "monotonic ascending", which is easily mentally shortened to just "ascending". Matter of taste. Humans tend to deal better with positive definitions than negative ones.

dead stores in ctor

        t_ = top -1;
        ...
        k_ = k - 1;
        k_t = k - top;

I don't get it. We compute these locals, and then never use them? Better to just elide them.

    int offsets[], t, t_, k, k_, k_t;

Oh, wait. They are object attributes, so they aren't dead stores. But, we don't like using the this convention in the ctor, even when not syntactically necessary? Recommend you add this, for emphasis.

I don't understand why the name kT isn't being used.

It's not obvious to me that any of these are actually needed or helpful. But if we retain them, at least rename to kMinusT, kMinus1, tMinus1.

It would be a kindness to the Gentle Reader to declare attributes in similar order to how ctor assigns them.

verb vs. noun

(or vs. adjective)

Consider changing the signature to

    void keep(int numKept, numValid) {

meaningful identifier

        int down = k_ - keep;

The meaning of the index down at this point is obscure. Add a // comment, or choose a more informative name.

In general, I'm looking for a loop variant in the keep() routine. The promise was to "distribute" values. There's no assert at the end verifying that, and I wouldn't know what to test if I wanted to add such an assertion.

Writing backwards if (0 < keep) expressions seems less helpful than letting me mentally pronounce if (keep > 0) as "if keep positive".

Eliding { } curly braces on single-statement if's makes reading the code much harder. I am continually feeling like I'm trusting the author not to trick me with misleading indents. Better to just expose the nesting structure by writing the braces.

class invariant

We need offsets[keep] to be valid, but it's unclear when that was established. It's not a Class Invariant, since ctor didn't touch that array. Similarly for candidates[--keep].

We are only told

        // keep up to k values of each potential rank ...
        ...
        // ... and next free offset

which is not enough.

The repeated candidates[ci] = Arrays.copyOf(many, k) sheds little light on what the invariant might be. I think it was just used to allocate storage?!?

I don't see a plan written down, that we will visit many in a certain order, and prune out losing entries following a certain pattern.

        int offset = 1;                // used in wrap-up

I still don't know the meaning of offset, and the code didn't explain it to me.

fatal error

            case 0: // shouldn't happen?!
                break;

Throw a fatal exception here, please. Then we will know it doesn't happen.

constant that changes

        for (int rank = t, top = Integer.MIN_VALUE ; 0 <= --rank ; ) {

Up in the ctor you told us that top is a synonym for t, and indeed we might mentally pronounce the latter as "top". But here we're using same identifier in a different scope to represent a different concept.

Choose a new name for the new concept.

comments lie!

This is just wrong.

    /** place top t of up to k values in candidates[t_][0:t] */
    private void handleFew(final E[] many) {
        final int n = many.length;
        if (n == t)
            return;

The contract is pretty clear. We evaluate for side effects, and the routine shall place t values into candidates.

It didn't.

Now, maybe the higher level application doesn't need it to. Which suggests that the spec is wrong. Fix the code to conform to the spec, or fix the spec.

It's unclear why {t == 1, t > 1} are distinct special cases. It's unclear why handleFew would need to make more than a single orderK() call, nor where its complexity is coming from. Up at the call site I thought it would be a nice trivial helper that makes an orderK() call and a copy.

automated test suite

This submission doesn't have one.

        System.out.println( Arrays.asList( ...'

That's a nice print statement, sure. But it's not self evaluating.

Crucially, it is a "big" test, we don't see any "small" unit tests of individual component routines.

And those routines are on the complex and slightly long side. If I could see them being exercised by unit tests, I might have a greater understanding now of the corner cases they handle, and greater confidence that they compute the right thing.

Near as I can tell, the global "found the top T entries!" assessment was done by manually eyeballing the output, rather than by having a component with access to global sort() verify that post-condition.

Sometimes I eyeball things correctly. I like the belt-n-suspenders backup of having an automated check.

\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ tracking calls to Arrays.sort() No. Calls to instantiation parameter OrderK<E> order. See "the original problem": you have no (direct) way to compare values, none of greater than, equal to, complements thereof or logical combinations, in the strictest form, not even identity. \$\endgroup\$
    – greybeard
    Dec 29, 2023 at 7:19
  • \$\begingroup\$ choose one of the several type-strong ways around this problem Please point me to more than one. \$\endgroup\$
    – greybeard
    Dec 29, 2023 at 7:20
2
+100
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ (Got bitten by inaccessible packages trying to give the full implementation a spin. Can you quote input size & count (&t&k) for some non-trivial input, t > 1, 1 < k-t < 9?) \$\endgroup\$
    – greybeard
    Dec 30, 2023 at 8:49
  • \$\begingroup\$ @greybeard, ummm, I thought I did that with self.assertEqual(num_distractors / 2 + 12, cnt["sort"]), given that we're groveling through ten thousand randomly shuffled array elements. \$\endgroup\$
    – J_H
    Dec 30, 2023 at 10:57
  • \$\begingroup\$ (thought I did that Probably, the DIY way. If only it ran straight away in my 3.5.2 installation. OTOH, that's the same but for constants as e.g. "the SO answer" or (presumably) Joop Eggen's determineTop()&determineTop2(). The whole point was to reduce this by a significant factor - and readably so.) \$\endgroup\$
    – greybeard
    Dec 30, 2023 at 16:03
  • \$\begingroup\$ Sometimes I eyeball things correctly. Sometimes I don't: While I never caught nonTopT not to work with smallish "random" input, it failed miserably with a moderate constructed Dutch flag one. Turns out I can't find a way to find a "neutral value for padding" short of running a full fledged tournament. \$\endgroup\$
    – greybeard
    Jan 1 at 8:39
  • \$\begingroup\$ Bounty awarded here for test cases & means. \$\endgroup\$
    – greybeard
    Jan 1 at 12:41
1
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Steps 1-6 are the basic solution, and nothing wrong with it but using that many calls to orderk() (handling candidates for 1st place & retiring k(5) - t(3) values each call). The basic idea to save calls is to handle candidates for 2nd place together, each call retiring (k-t+1), 3rd(k-t+2), … until a final cleanup. When doing it in phases as started in the paragraph below that numbered list, you need O(n) additional space. \$\endgroup\$
    – greybeard
    Dec 29, 2023 at 18:54
  • \$\begingroup\$ You caught me not sufficiently reading the details & decisions. You might want to formulate your solution first more abstractly. Very interesting, if it weren't Christmas time. \$\endgroup\$
    – Joop Eggen
    Dec 29, 2023 at 20:55
  • \$\begingroup\$ I might appreciate an elaboration in your answer of how to implement that suggestion in the code - the "non-doc-comment" above public void topByOrderK() does look overly terse from where I stand now, and was fresh (here) when I started a bounty mere hours before Reinderien answered. \$\endgroup\$
    – greybeard
    Dec 29, 2023 at 23:47
  • \$\begingroup\$ I tried, but not very successfully. Added code and a bit of style. I agree with your assessment on the complexity. In fact you probably have a better idea what would still be possible. \$\endgroup\$
    – Joop Eggen
    Dec 30, 2023 at 2:33
  • \$\begingroup\$ not sure this code indeed looks better (don't I recognise that feeling) determineTop2() sure highlights that I may have indiscriminately accumulated constraints like neither mutation of the input nor O(n) additional space (not put into the question purposefully) until the difficulty of implementation overwhelmed me. \$\endgroup\$
    – greybeard
    Dec 30, 2023 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.