Thread overview | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
February 09, 2012 Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
I have a doubt about the best way to insert and move (not replace) some data on an array. For example, In some cases if I want to do action above, I do a loop moving the data until the point that I want and finally I insert the new data there. In D I did this: begin code . . . int[] arr = [0,1,2,3,4,5,6,7,8,9]; arr.insertInPlace(position, newValue); arr.popBack(); . . . end code After the insertInPlace my array changed it's length to 11, so I use arr.popBack(); to keep the array length = 10; The code above is working well, I just want know if is there a better way? Thanks, Matheus. |
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to MattCodr Attachments:
| I __believe__ that insertInPlace doesn't shift the elements, but use an
appender allocating another array instead.
Maybe this function do what you want.
int[] arr = [0,1,2,3,4,5,6,7,8,9];
void maybe(T)(T[] arr, size_t pos, T value) {
size_t i;
for (i = arr.length - 1; i > pos; i--) {
arr[i] = arr[i-1];
}
arr[i] = value;
}
maybe(arr, 3, 0);
maybe(arr, 0, 1);
assert(arr == [1, 0, 1, 2, 0, 3, 4, 5, 6, 7]);
2012/2/9 MattCodr <matheus_nab@hotmail.com>
> I have a doubt about the best way to insert and move (not replace) some
> data on an array.
>
> For example,
>
> In some cases if I want to do action above, I do a loop moving the data until the point that I want and finally I insert the new data there.
>
>
> In D I did this:
>
> begin code
> .
> .
> .
> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>
> arr.insertInPlace(position, newValue);
> arr.popBack();
> .
> .
> .
> end code
>
>
> After the insertInPlace my array changed it's length to 11, so I use arr.popBack(); to keep the array length = 10;
>
> The code above is working well, I just want know if is there a better way?
>
> Thanks,
>
> Matheus.
>
|
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to Pedro Lacerda | On Thursday, 9 February 2012 at 12:51:09 UTC, Pedro Lacerda wrote: > I __believe__ that insertInPlace doesn't shift the elements, Yes, It appears that it really doesn't shift the array, insertInPlace just returns a new array with a new element in n position. > Maybe this function do what you want. > > > int[] arr = [0,1,2,3,4,5,6,7,8,9]; > > void maybe(T)(T[] arr, size_t pos, T value) { > size_t i; > for (i = arr.length - 1; i > pos; i--) { > arr[i] = arr[i-1]; > } > arr[i] = value; > } > In fact, I usually wrote functions as you did. I just looking for a new way to do that with D and Phobos lib. Thanks, Matheus. |
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to MattCodr | On 02/09/2012 03:47 AM, MattCodr wrote:
> I have a doubt about the best way to insert and move (not replace) some
> data on an array.
>
> For example,
>
> In some cases if I want to do action above, I do a loop moving the data
> until the point that I want and finally I insert the new data there.
>
>
> In D I did this:
>
> begin code
> .
> .
> .
> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>
> arr.insertInPlace(position, newValue);
> arr.popBack();
> .
> .
> .
> end code
>
>
> After the insertInPlace my array changed it's length to 11, so I use
> arr.popBack(); to keep the array length = 10;
>
> The code above is working well, I just want know if is there a better way?
>
> Thanks,
>
> Matheus.
Most straightforward that I know of is the following:
arr = arr[0 .. position] ~ [ newValue ] ~ arr[position + 1 .. $];
But if you don't actually want to modify the data, you can merely access the elements in-place by std.range.chain:
import std.stdio;
import std.range;
void main()
{
int[] arr = [0,1,2,3,4,5,6,7,8,9];
immutable position = arr.length / 2;
immutable newValue = 42;
auto r = chain(arr[0 .. position], [ newValue ], arr[position + 1 .. $]);
writeln(r);
}
'r' above is a lazy range that just provides access to the three ranges given to it. 'arr' does not change in any way.
Ali
|
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli | On Thu, Feb 09, 2012 at 10:30:22AM -0800, Ali Çehreli wrote: [...] > But if you don't actually want to modify the data, you can merely access the elements in-place by std.range.chain: > > import std.stdio; > import std.range; > > void main() > { > int[] arr = [0,1,2,3,4,5,6,7,8,9]; > immutable position = arr.length / 2; > immutable newValue = 42; > > auto r = chain(arr[0 .. position], [ newValue ], arr[position + > 1 .. $]); > writeln(r); > } > > 'r' above is a lazy range that just provides access to the three ranges given to it. 'arr' does not change in any way. [...] Wow! This is really cool. So you *can* have O(1) insertions in the middle of an array after all. :) Of course, you probably want to flatten it once in a while to keep random access cost from skyrocketing. (I'm assuming delegates or something equivalent are involved in generating the lazy range?) T -- Give a man a fish, and he eats once. Teach a man to fish, and he will sit forever. |
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli | On Thursday, 9 February 2012 at 18:30:22 UTC, Ali Çehreli wrote:
> On 02/09/2012 03:47 AM, MattCodr wrote:
>> I have a doubt about the best way to insert and move (not replace) some
>> data on an array.
>>
>> For example,
>>
>> In some cases if I want to do action above, I do a loop moving the data
>> until the point that I want and finally I insert the new data there.
>>
>>
>> In D I did this:
>>
>> begin code
>> .
>> .
>> .
>> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>>
>> arr.insertInPlace(position, newValue);
>> arr.popBack();
>> .
>> .
>> .
>> end code
>>
>>
>> After the insertInPlace my array changed it's length to 11, so I use
>> arr.popBack(); to keep the array length = 10;
>>
>> The code above is working well, I just want know if is there a better way?
>>
>> Thanks,
>>
>> Matheus.
>
> Most straightforward that I know of is the following:
>
> arr = arr[0 .. position] ~ [ newValue ] ~ arr[position + 1 .. $];
>
> But if you don't actually want to modify the data, you can merely access the elements in-place by std.range.chain:
>
> import std.stdio;
> import std.range;
>
> void main()
> {
> int[] arr = [0,1,2,3,4,5,6,7,8,9];
> immutable position = arr.length / 2;
> immutable newValue = 42;
>
> auto r = chain(arr[0 .. position], [ newValue ], arr[position + 1 .. $]);
> writeln(r);
> }
>
> 'r' above is a lazy range that just provides access to the three ranges given to it. 'arr' does not change in any way.
>
> Ali
Hi Ali,
You gave me a tip with this "chain" feature.
I changed a few lines of your code, and it worked as I wanted:
import std.stdio;
import std.range;
import std.array;
void main()
{
int[] arr = [0,1,2,3,4,5,6,7,8,9];
immutable position = arr.length / 2;
immutable newValue = 42;
auto r = chain(arr[0 .. position], [ newValue ], arr[position .. $-1]);
arr = array(r);
foreach(int i; arr)
writefln("%d", i);
}
Thanks,
Matheus.
|
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | On 02/09/2012 11:03 AM, H. S. Teoh wrote: > On Thu, Feb 09, 2012 at 10:30:22AM -0800, Ali Çehreli wrote: > [...] >> But if you don't actually want to modify the data, you can merely >> access the elements in-place by std.range.chain: >> >> import std.stdio; >> import std.range; >> >> void main() >> { >> int[] arr = [0,1,2,3,4,5,6,7,8,9]; >> immutable position = arr.length / 2; >> immutable newValue = 42; >> >> auto r = chain(arr[0 .. position], [ newValue ], arr[position + >> 1 .. $]); >> writeln(r); >> } >> >> 'r' above is a lazy range that just provides access to the three >> ranges given to it. 'arr' does not change in any way. > [...] > > Wow! This is really cool. So you *can* have O(1) insertions in the > middle of an array after all. :) > > Of course, you probably want to flatten it once in a while to keep > random access cost from skyrocketing. O(1) would be violated only if there are too many actual ranges. > (I'm assuming delegates or > something equivalent are involved in generating the lazy range?) Simpler than that. :) The trick is that chain() returns a range object that operates lazily. I have used chain() as an example for finite RandomAccessRange types (I used the name 'Together' instead of Chain). Search for "Finite RandomAccessRange" here: http://ddili.org/ders/d.en/ranges.html And yes, I note there that the implementation is not O(1). Also look under the title "Laziness" in that chapter. Ali |
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to MattCodr | On 02/09/2012 08:20 PM, MattCodr wrote:
> On Thursday, 9 February 2012 at 18:30:22 UTC, Ali Çehreli wrote:
>> On 02/09/2012 03:47 AM, MattCodr wrote:
>>> I have a doubt about the best way to insert and move (not replace) some
>>> data on an array.
>>>
>>> For example,
>>>
>>> In some cases if I want to do action above, I do a loop moving the data
>>> until the point that I want and finally I insert the new data there.
>>>
>>>
>>> In D I did this:
>>>
>>> begin code
>>> .
>>> .
>>> .
>>> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>>>
>>> arr.insertInPlace(position, newValue);
>>> arr.popBack();
>>> .
>>> .
>>> .
>>> end code
>>>
>>>
>>> After the insertInPlace my array changed it's length to 11, so I use
>>> arr.popBack(); to keep the array length = 10;
>>>
>>> The code above is working well, I just want know if is there a better
>>> way?
>>>
>>> Thanks,
>>>
>>> Matheus.
>>
>> Most straightforward that I know of is the following:
>>
>> arr = arr[0 .. position] ~ [ newValue ] ~ arr[position + 1 .. $];
>>
>> But if you don't actually want to modify the data, you can merely
>> access the elements in-place by std.range.chain:
>>
>> import std.stdio;
>> import std.range;
>>
>> void main()
>> {
>> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>> immutable position = arr.length / 2;
>> immutable newValue = 42;
>>
>> auto r = chain(arr[0 .. position], [ newValue ], arr[position + 1 .. $]);
>> writeln(r);
>> }
>>
>> 'r' above is a lazy range that just provides access to the three
>> ranges given to it. 'arr' does not change in any way.
>>
>> Ali
>
> Hi Ali,
>
> You gave me a tip with this "chain" feature.
>
> I changed a few lines of your code, and it worked as I wanted:
>
>
> import std.stdio;
> import std.range;
> import std.array;
>
> void main()
> {
> int[] arr = [0,1,2,3,4,5,6,7,8,9];
> immutable position = arr.length / 2;
> immutable newValue = 42;
>
> auto r = chain(arr[0 .. position], [ newValue ], arr[position .. $-1]);
> arr = array(r);
>
> foreach(int i; arr)
> writefln("%d", i);
> }
>
>
> Thanks,
>
> Matheus.
>
Note that this code does the same, but is more efficient if you don't actually need the array:
import std.stdio;
import std.range;
import std.array;
void main()
{
int[] arr = [0,1,2,3,4,5,6,7,8,9];
immutable position = arr.length / 2;
immutable newValue = 42;
auto r = chain(arr[0 .. position], [ newValue ], arr[position .. $-1]);
foreach(i; r)
writefln("%d", i);
}
|
February 09, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On Thursday, 9 February 2012 at 19:49:43 UTC, Timon Gehr wrote:
> Note that this code does the same, but is more efficient if you don't actually need the array:
Yes I know, In fact I need re-think the way I code with this new features of D, like ranges for example.
Thanks,
Matheus.
|
February 10, 2012 Re: Arrays - Inserting and moving data | ||||
---|---|---|---|---|
| ||||
Posted in reply to MattCodr | Am 09.02.2012, 22:03 Uhr, schrieb MattCodr <matheus_nab@hotmail.com>:
> On Thursday, 9 February 2012 at 19:49:43 UTC, Timon Gehr wrote:
>> Note that this code does the same, but is more efficient if you don't actually need the array:
>
> Yes I know, In fact I need re-think the way I code with this new features of D, like ranges for example.
>
> Thanks,
>
> Matheus.
I know that feeling. I had no exposure to functional programming and options like chain never come to my head. Although "map" is a concept that I made friends with early.
|
Copyright © 1999-2021 by the D Language Foundation