On Tue, Apr 19, 2022 at 09:16:18PM +0000, Dom DiSc via Digitalmars-d wrote:
> On Tuesday, 19 April 2022 at 16:35:21 UTC, H. S. Teoh wrote:
> > Just thought I'd pick all the bright minds here: I have a set of numbers in string form (as decimal digits), stored in a trie.  How do I retrieve the largest number in the set?
> 
> Is it necessary to store decimal numbers?
> Because if they would be stored binary, the highest number would
> automatically be among the longest strings.

Obviously, the same holds for decimal numbers.  The question is, how to efficiently locate it in the trie (without traversing the entire trie).


T

-- 
A linguistics professor was lecturing to his class one day. "In English," he said, "A double negative forms a positive. In some languages, though, such as Russian, a double negative is still a negative. However, there is no language wherein a double positive can form a negative." A voice from the back of the room piped up, "Yeah, yeah."

On 4/19/22 14:28, H. S. Teoh wrote:
> On Tue, Apr 19, 2022 at 09:16:18PM +0000, Dom DiSc via Digitalmars-d wrote:

>> Is it necessary to store decimal numbers?
>> Because if they would be stored binary, the highest number would
>> automatically be among the longest strings.
>
> Obviously, the same holds for decimal numbers.

I think Dom DiSc meant zero pad all numbers to have the same maximum length? If there is indeed a maximum length that does not incur too much cost (I think tries naturally don't have that kind of cost?), then the rightmost will be the highest number. (?)

Ali

On Tue, Apr 19, 2022 at 02:37:07PM -0700, Ali Çehreli via Digitalmars-d wrote:
> On 4/19/22 14:28, H. S. Teoh wrote:
> > On Tue, Apr 19, 2022 at 09:16:18PM +0000, Dom DiSc via Digitalmars-d
> wrote:
> 
> >> Is it necessary to store decimal numbers?
> >> Because if they would be stored binary, the highest number would
> >> automatically be among the longest strings.
> >
> > Obviously, the same holds for decimal numbers.
> 
> I think Dom DiSc meant zero pad all numbers to have the same maximum length?  If there is indeed a maximum length that does not incur too much cost (I think tries naturally don't have that kind of cost?), then the rightmost will be the highest number. (?)
[...]

!!! Ali, you're a genius!  Pad the numbers with 0's up to some maximum number of digits (for this particular trie I'm not expecting more than a handful of digits anyway), and that would ensure numerical order == lexicographic order, so the problem becomes trivial. It also simultaneously solves a bunch of other issues I have, all stemming from the fact that with digit strings of non-equal lengths, numerical order != lexicographic order.

Thanks!!!


T

-- 
Why have vacation when you can work?? -- EC

On Tue, Apr 19, 2022 at 05:12:30PM -0700, H. S. Teoh via Digitalmars-d wrote:
> On Tue, Apr 19, 2022 at 02:37:07PM -0700, Ali Çehreli via Digitalmars-d wrote:
[...]
> !!! Ali, you're a genius!  Pad the numbers with 0's up to some maximum number of digits (for this particular trie I'm not expecting more than a handful of digits anyway), and that would ensure numerical order == lexicographic order, so the problem becomes trivial. It also simultaneously solves a bunch of other issues I have, all stemming from the fact that with digit strings of non-equal lengths, numerical order != lexicographic order.
[...]

Hmm, actually, it turns out that padding with 0's breaks the very reason I'm using a trie in the first place (it's for detecting potential matches of a set of numbers based on an incomplete input prefix). So it's a no-go, even though it was a genius idea. :-(

Looks like the best solution is just to separately index the set with a sorted linear array... Steven's idea of storing max lengths in each node does work for this specific problem, but it makes other operations needlessly hard.  So also no-go. :-/


T

-- 
Be in denial for long enough, and one day you'll deny yourself of things you wish you hadn't.