(And not talking about some cheesy insertion sort!!)

If you build an array once and for all, and all you want
is to do binary search on it later, it doesn't make sense to
allocate that big contiguous .data. I'd rather leave it
as an appender.

--jm


On Wednesday, 22 February 2012 at 23:22:35 UTC, Juan Manuel Cabo wrote:
>> No, because the array doesn't actually exist until appender makes copy.
>
> Will one be able to use the sort!()() algorithm directly on your appender,
> that is, without accessing/creating the underlying array?
>
> --jm

On Thursday, February 23, 2012 01:38:05 Juan Manuel Cabo wrote:
> (And not talking about some cheesy insertion sort!!)
> 
> If you build an array once and for all, and all you want
> is to do binary search on it later, it doesn't make sense to
> allocate that big contiguous .data. I'd rather leave it
> as an appender.
> 
> --jm
> 
> 
> On Wednesday, 22 February 2012 at 23:22:35 UTC, Juan Manuel Cabo
> 
> wrote:
> >> No, because the array doesn't actually exist until appender makes copy.
> > 
> > Will one be able to use the sort!()() algorithm directly on
> > your appender,
> > that is, without accessing/creating the underlying array?

If appender ends up with multiple arrays in it, then random access is no longer O(1) and is therefore unacceptable. As such, most sort algorithms wouldn't work with it.

Also, your bit about using appender to pass an array around wouldn't work either, because it wouldn't simply be wrapper around an array anymore.

- Jonathan M Davis


P.S. Please don't top post. Replies should go _after_ the preceding message.

On Wed, Feb 22, 2012 at 07:51:27PM -0500, Jonathan M Davis wrote: [...]
> P.S. Please don't top post. Replies should go _after_ the preceding message.

Answer: Because it breaks the normal flow of conversation.

Question: Why is it bad to top-post?


T

-- 
Why waste time learning, when ignorance is instantaneous? -- Hobbes, from Calvin & Hobbes

On Wed, 22 Feb 2012 18:51:27 -0600, Jonathan M Davis <jmdavisProg@gmx.com> wrote:
> On Thursday, February 23, 2012 01:38:05 Juan Manuel Cabo wrote:
>> (And not talking about some cheesy insertion sort!!)
>>
>> If you build an array once and for all, and all you want
>> is to do binary search on it later, it doesn't make sense to
>> allocate that big contiguous .data. I'd rather leave it
>> as an appender.
>>
>> --jm
>>
>>
>> On Wednesday, 22 February 2012 at 23:22:35 UTC, Juan Manuel Cabo
>>
>> wrote:
>> >> No, because the array doesn't actually exist until appender
>> >> makes copy.
>> >
>> > Will one be able to use the sort!()() algorithm directly on
>> > your appender,
>> > that is, without accessing/creating the underlying array?
>
> If appender ends up with multiple arrays in it, then random access is no
> longer O(1) and is therefore unacceptable. As such, most sort algorithms
> wouldn't work with it.
>
> Also, your bit about using appender to pass an array around wouldn't work
> either, because it wouldn't simply be wrapper around an array anymore.
>
> - Jonathan M Davis
>
>
> P.S. Please don't top post. Replies should go _after_ the preceding message.

Well, a VList (which is a list of arrays) is has O(1) amortized indexing. Actual performance of my implementation would be O(N / (4080/T.sizeof)), which isn't so bad. And anything under a page of ram would be O(1).

On Thursday, 23 February 2012 at 00:51:38 UTC, Jonathan M Davis wrote:
[...]
> If appender ends up with multiple arrays in it, then random access is no longer O(1) and is therefore unacceptable. As such, most sort algorithms wouldn't work with it.

If all I want is binary search on a big appender, then it
is O(k * n * log(n)), and that k right there doesn't
bother me. Also, binary search is absolutely not
cpu cache friendly to begin with.

> Also, your bit about using appender to pass an array around wouldn't work either, because it wouldn't simply be wrapper
> around an array anymore.
>
> - Jonathan M Davis

Yeah, but I don't care about the underlying array. I care
about multiple places referencing the same Appender. If I
from any place that references it, it appends to the same
appender. The Appender "array" has identity. Ranges do not:

     int[] bla = [1,2,3];
     int[] ble = bla;
     ble ~= 4;
     assert(bla.length == 3);

This is very easy to solve with appender.
This is what happens in Java:
    ArrayList<Integer> bla = new ArrayList<Integer>();
    bla.add(1);
    ArrayList<Integer> ble = bla;
    ble.add(2);
    //prints 2
    System.out.println(Integer.toString(bla.size()));
    //prints 2
    System.out.println(Integer.toString(ble.size()));

(yikes, aint that verbose!)
The ArrayList has identity. It is a class, so that it
many variables reference the _same_ object.
(this can be accomplished with structs too though, but
not with ranges).

>
>
> P.S. Please don't top post. Replies should go _after_ the preceding message.

Sorry, got it.

--jm

On Thursday, 23 February 2012 at 01:36:32 UTC, Juan Manuel Cabo wrote:
> If all I want is binary search on a big appender, then it
> is O(k * n * log(n)), and that k right there doesn't
> bother me.

(Where binary search is of course O(log(n))
and accessing individual elements with the proposed
Appender is O(N / (4080/T.sizeof)), so k == 4080/T.sizeof)

--jm

On Thursday, 23 February 2012 at 00:51:38 UTC, Jonathan M Davis wrote:
> P.S. Please don't top post. Replies should go _after_ the preceding message.

P.S: You are right though, that it wouldn't be O(1) anymore
and it should be said big in the documentation that it is
amortized.

--jm

On Thursday, February 23, 2012 02:36:31 Juan Manuel Cabo wrote:
> Yeah, but I don't care about the underlying array. I care about multiple places referencing the same Appender. If I from any place that references it, it appends to the same appender. The Appender "array" has identity. Ranges do not:
> 
> int[] bla = [1,2,3];
> int[] ble = bla;
> ble ~= 4;
> assert(bla.length == 3);
> 
> This is very easy to solve with appender.
> This is what happens in Java:
> ArrayList<Integer> bla = new ArrayList<Integer>();
> bla.add(1);
> ArrayList<Integer> ble = bla;
> ble.add(2);
> //prints 2
> System.out.println(Integer.toString(bla.size()));
> //prints 2
> System.out.println(Integer.toString(ble.size()));
> 
> (yikes, aint that verbose!)
> The ArrayList has identity. It is a class, so that it
> many variables reference the _same_ object.
> (this can be accomplished with structs too though, but
> not with ranges).

The D equivalent would really be Array, not Appender. I'm not sure that it's a great idea to use Appender as a container - particularly when there are types specifically intended to be used as containers. Appender is geared specifically towards array building (like StringBuilder in Java, except generalized for all arrays). If it's a container that you're looking for, then I really think that you should use a container.

- Jonathan M Davis

On Thursday, 23 February 2012 at 01:36:32 UTC, Juan Manuel Cabo wrote:
> On Thursday, 23 February 2012 at 00:51:38 UTC, Jonathan M Davis wrote:
> [...]
>> If appender ends up with multiple arrays in it, then random access is no longer O(1) and is therefore unacceptable. As such, most sort algorithms wouldn't work with it.
>
> If all I want is binary search on a big appender, then it
> is O(k * n * log(n)), and that k right there doesn't
> bother me. Also, binary search is absolutely not
> cpu cache friendly to begin with.
>
>> Also, your bit about using appender to pass an array around wouldn't work either, because it wouldn't simply be wrapper
>> around an array anymore.
>>
>> - Jonathan M Davis
>
> Yeah, but I don't care about the underlying array. I care
> about multiple places referencing the same Appender. If I
> from any place that references it, it appends to the same
> appender. The Appender "array" has identity. Ranges do not:
>
>      int[] bla = [1,2,3];
>      int[] ble = bla;
>      ble ~= 4;
>      assert(bla.length == 3);
>
> This is very easy to solve with appender.
> This is what happens in Java:
>     ArrayList<Integer> bla = new ArrayList<Integer>();
>     bla.add(1);
>     ArrayList<Integer> ble = bla;
>     ble.add(2);
>     //prints 2
>     System.out.println(Integer.toString(bla.size()));
>     //prints 2
>     System.out.println(Integer.toString(ble.size()));
>
> (yikes, aint that verbose!)
> The ArrayList has identity. It is a class, so that it
> many variables reference the _same_ object.
> (this can be accomplished with structs too though, but
> not with ranges).

I meant ref counted structs.

>
>>
>>
>> P.S. Please don't top post. Replies should go _after_ the preceding message.
>
> Sorry, got it.
>
> --jm

On Wed, 22 Feb 2012 19:57:37 -0600, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Thursday, February 23, 2012 02:36:31 Juan Manuel Cabo wrote:
>> Yeah, but I don't care about the underlying array. I care
>> about multiple places referencing the same Appender. If I
>> from any place that references it, it appends to the same
>> appender. The Appender "array" has identity. Ranges do not:
>>
>> int[] bla = [1,2,3];
>> int[] ble = bla;
>> ble ~= 4;
>> assert(bla.length == 3);
>>
>> This is very easy to solve with appender.
>> This is what happens in Java:
>> ArrayList<Integer> bla = new ArrayList<Integer>();
>> bla.add(1);
>> ArrayList<Integer> ble = bla;
>> ble.add(2);
>> //prints 2
>> System.out.println(Integer.toString(bla.size()));
>> //prints 2
>> System.out.println(Integer.toString(ble.size()));
>>
>> (yikes, aint that verbose!)
>> The ArrayList has identity. It is a class, so that it
>> many variables reference the _same_ object.
>> (this can be accomplished with structs too though, but
>> not with ranges).
>
> The D equivalent would really be Array, not Appender. I'm not sure that it's a
> great idea to use Appender as a container - particularly when there are types
> specifically intended to be used as containers. Appender is geared specifically
> towards array building (like StringBuilder in Java, except generalized for all
> arrays). If it's a container that you're looking for, then I really think that
> you should use a container.
>
> - Jonathan M Davis

StringBuilder in .Net is implemented using lists and doesn't expose iteration nor indexing; why are we worrying about the indexing and container performance of D's appender?