Thread overview | |||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
December 14, 2014 Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
What's the fastest way to append multiple elements to an array?: Either arr ~= e1; arr ~= e2; arr ~= e3; or arr ~= [e1,e2,e3]; or some other trick? |
December 14, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On 15.12.14 00:16, "Nordlöw" wrote:
> or some other trick?
void append(T, Args...)(ref T[] arr, Args args){
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = args[i];
}
void main()
{
int[] arr = [1, 2, 3, 4, 5];
arr.append(3, 10, 14);
writeln(arr);
}
output:
[1, 2, 3, 4, 5, 3, 10, 14]
|
December 15, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to zeljkog | On Sunday, 14 December 2014 at 23:52:15 UTC, zeljkog wrote:
> void append(T, Args...)(ref T[] arr, Args args){
> arr.length += args.length;
> foreach(i, e; args)
> arr[$ - args.length + i] = args[i];
> }
Isn't this algorithm already encoded somewhere in Phobos?
|
December 15, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On 15.12.14 01:00, "Nordlöw" wrote:
> Isn't this algorithm already encoded somewhere in Phobos?
I don't know.
|
December 15, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to zeljkog | On Sunday, 14 December 2014 at 23:52:15 UTC, zeljkog wrote: > On 15.12.14 00:16, "Nordlöw" wrote: >> or some other trick? > > void append(T, Args...)(ref T[] arr, Args args){ > arr.length += args.length; > foreach(i, e; args) > arr[$ - args.length + i] = args[i]; > } > > > void main() > { > int[] arr = [1, 2, 3, 4, 5]; > arr.append(3, 10, 14); > writeln(arr); > } > > output: > [1, 2, 3, 4, 5, 3, 10, 14] Maybe *std.array.Appender* should be used in append(). (http://dlang.org/phobos/std_array.html#.Appender) Even if i often myself feel too lazy to use it and use only the concat. op instead. |
December 15, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On Sunday, 14 December 2014 at 23:16:12 UTC, Nordlöw wrote: > What's the fastest way to append multiple elements to an array?: > > Either > > arr ~= e1; > arr ~= e2; > arr ~= e3; > > or > > arr ~= [e1,e2,e3]; > > or some other trick? It does somewhat depend on context but std.array.appender is generally a good choice. It supports appending elements individually, appending a range of elements and manually reserving extra space. E.g. auto app = appender(somePreExistingArray); app ~= e0; app ~= [e1, e2]; app.reserve(3); //eagerly ensures that there's 3 elements capacity, //guaranteeing at most one re-allocation for adding the following 3 elements app ~= e3; app ~= e4; app ~= e5; or my personal favourite: app ~= only(e6, e7, e8, e9); When you append a range to an appender it will use the length of the range (if available) to reserve space ahead-of-time. There is a (small) cost to creating an appender, so you ideally don't want to make a new one every time you add a couple of elements (this isn't a deficiency in appender, it's just how GC slices are in D). |
December 15, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On 12/14/14 6:16 PM, "Nordlöw" wrote: > What's the fastest way to append multiple elements to an array?: Before appending, call reserve to avoid the possibility of reallocating multiple times: arr.reserve(arr.length + n); // about to append n elements. > Either > > arr ~= e1; > arr ~= e2; > arr ~= e3; > > or > > arr ~= [e1,e2,e3]; I wish this would be fastest, but it's not, because this allocates an array on the heap with elements e1, e2, e3 before appending. It would be a superb addition to D if this would simply allocate a stack array (if the array never escapes the expression). -Steve |
December 15, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | On Monday, 15 December 2014 at 15:55:22 UTC, Steven Schveighoffer wrote: >> What's the fastest way to append multiple elements to an array?: > > Before appending, call reserve to avoid the possibility of reallocating multiple times: > > arr.reserve(arr.length + n); // about to append n elements. Thanks! > >> Either >> >> arr ~= e1; >> arr ~= e2; >> arr ~= e3; >> >> or >> >> arr ~= [e1,e2,e3]; > > I wish this would be fastest, but it's not, because this allocates an array on the heap with elements e1, e2, e3 before appending. It would be a superb addition to D if this would simply allocate a stack array (if the array never escapes the expression). That's what I thought :) |
December 17, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | On 15.12.14 01:00, "Nordlöw" wrote:
> Isn't this algorithm already encoded somewhere in Phobos?
void append(T, Args...)(ref T[] arr, auto ref Args args){
{
static if (args.length == 1)
arr ~= args[0]; // inlined
else{
arr.length += args.length;
foreach(i, e; args)
arr[$ - args.length + i] = e;
}
}
I've just tested, this looks usable.
Equal for 1 item, considerably (~40%) faster for 2, and much (100+%) faster for more.
Also more convenient.
Maybe samthing like that should go to Fobos.
|
December 17, 2014 Re: Fastest Way to Append Multiple Elements to an Array | ||||
---|---|---|---|---|
| ||||
Posted in reply to zeljkog | On Wednesday, 17 December 2014 at 11:15:30 UTC, zeljkog wrote:
> On 15.12.14 01:00, "Nordlöw" wrote:
>> Isn't this algorithm already encoded somewhere in Phobos?
>
> void append(T, Args...)(ref T[] arr, auto ref Args args){
> {
> static if (args.length == 1)
> arr ~= args[0]; // inlined
> else{
> arr.length += args.length;
> foreach(i, e; args)
> arr[$ - args.length + i] = e;
> }
> }
>
> I've just tested, this looks usable.
> Equal for 1 item, considerably (~40%) faster for 2, and much (100+%) faster for more.
> Also more convenient.
>
> Maybe samthing like that should go to Fobos.
I don't think you can beat appender. And your function does not accept ranges, only elements. I would write it like this:
---
void append(T, Args...)(ref T[] data, Args args)
{
static size_t estimateLength(Args args)
{
size_t result;
foreach(e; args)
static if(hasLength!(typeof(e)))
result += e.length;
else
result += 1;
return result;
}
auto app = appender!(T[])(data);
app.reserve(data.length + estimateLength(args));
foreach(e; args)
app.put(e);
data = app.data;
}
void main()
{
import std.stdio;
int[] data;
append(data, 1, 2, only(1, 2, 3), iota(4, 9));
writeln(data);
}
---
Maybe appender.put should get an overload that does the same, though I didn't had the need for it yet.
|
Copyright © 1999-2021 by the D Language Foundation