On Thu, May 23, 2019 at 1:38 PM Lukasz Cwik <lc...@google.com> wrote:
>
>
> On Thu, May 23, 2019 at 11:37 AM Rui Wang <ruw...@google.com> wrote:
>
>> A few obvious problems with this code:
>>> 1. Removing the elements already processed from the bag requires
>>> clearing and rewriting the entire bag. This is O(n^2) in the number of
>>> input trades.
>>>
>> why it's not O(2 * n) to clearing and rewriting trade state?
>>
>>
>>> public interface SortedMultimapState<K, V> extends State {
>>> // Add a value to the map.
>>> void put(K key, V value);
>>> // Get all values for a given key.
>>> ReadableState<Iterable<V>> get(K key);
>>> // Return all entries in the map.
>>> ReadableState<Iterable<KV<K, V>>> allEntries();
>>> // Return all entries in the map with keys <= limit. returned elements
>>> are sorted by the key.
>>> ReadableState<Iterable<KV<K, V>>> entriesUntil(K limit);
>>>
>> // Remove all values with the given key;
>>> void remove(K key);
>>> // Remove all entries in the map with keys <= limit.
>>> void removeUntil(K limit);
>>>
>> Will removeUntilExcl(K limit) also useful? It will remove all entries in
>> the map with keys < limit.
>>
>>
>>> Runners will sort based on the encoded value of the key. In order to
>>> make this easier for users, I propose that we introduce a new tag on Coders
>>> *PreservesOrder*. A Coder that contains this tag guarantees that the
>>> encoded value preserves the same ordering as the base Java type.
>>>
>>
>> Could you clarify what is "encoded value preserves the same ordering as
>> the base Java type"?
>>
>
> Lets say A and B represent two different instances of the same Java type
> like a double, then A < B (using the languages comparison operator) iff
> encode(A) < encode(B) (note the encoded versions are compared
> lexicographically)
>
Since coders are shared across SDKs, do we expect A < B iff e(A) < e(P)
property to hold for all languages we support? What happens A, B sort
differently in different languages?
>
>
>
>>
>> -Rui
>>
>
