Re: Hash Tables in D
WBvDda> http://minas-mina.com/2016/01/01/associative-arrays/ This article translated into Russian: http://habrahabr.ru/post/274723/ -- With best regards from Ukraine, Andre Skype: Francophile Twitter: @m_elensule; Facebook: menelion
Re: Hash Tables in D
On 2016-01-07 15:11, Steven Schveighoffer wrote:
With dcollections [1] I had a feature called "purging" where you would
iterate over a collection like this:
foreach(ref bool removeIt, int val; collection)
{
if(someCondition) removeIt = true;
}
The entire reason for this is because you can do something similar in
C++ containers, and I found it absolutely annoying that the existing
container classes don't allow this. A very frequent use of containers is
to iterate through picking which ones should be removed (think of a cache)
In Ruby that's called "reject", i.e. the opposite of "filter".
--
/Jacob Carlborg
Re: Hash Tables in D
On Sunday, 3 January 2016 at 19:29:05 UTC, Martin Nowak wrote: There is a bug. You should never do this b/c of iterator/range invalidation. foreach (key; aa.keys) aa.remove(key); I've recently hit this when trying to remove some of the elements from an AA while iterating over it. It's easy to forget that it is not allowed, especially when working on more complex algorithms. Accidentally, it worked all fine even with large data sets with DMD 2.069, but with GDC mysterious segfaults appeared - the first thought in such case was obviously a bug in GDC or in the older front-end. However, this is a very convenient, natural and intuitive syntax for something that is needed quite frequently, yet this code breaks silently in non-predictable ways. There are already registered issues concerning this (or similar with insertion) problem, including: https://issues.dlang.org/show_bug.cgi?id=4179 https://issues.dlang.org/show_bug.cgi?id=2255 https://issues.dlang.org/show_bug.cgi?id=10821 https://issues.dlang.org/show_bug.cgi?id=10876 https://issues.dlang.org/show_bug.cgi?id=13903 I've personally encountered segfaults, infinite loops, programs producing incorrect results. Some solutions to this were proposed in the bug reports - either: a) explicitly allow removing during iteration, and make sure it always works, or b) explicitly disallow removing during iteration, and always throw an Error whenever it is attempted. In some cases it could even be detectable in compile time. And I don't mean including a single sentence about this somewhere in the docs. I mean an error reported by the compiler and/or runtime. The runtime checks could be disabled for -release, but there should be at least an option to detect such errors. Probably the worst part of it is that you're free to wrap it in @safe, while it's not safe at all.
Re: Hash Tables in D
On 06 Jan 2016 3:25 PM, "Minas Mina via Digitalmars-d-announce" <
digitalmars-d-announce@puremagic.com> wrote:
>
> On Wednesday, 6 January 2016 at 12:19:45 UTC, Jacob Carlborg wrote:
>>
>> On 2016-01-05 15:44, Minas Mina wrote:
>>
>>> It won't, but to use it again you need to allocate a new one (If I'm not
>>> mistaken).
>>
>>
>> Not explicitly. I don't know if the runtime allocates a new one. This
works:
>>
>> void main()
>> {
>> auto foo = ["foo" : 1];
>> foo = null;
>> foo["bar"] = 2;
>> assert(foo["bar"] == 2);
>> }
>
>
> I believe it does, check out this example:
> import std.stdio;
>
> class C
> {
> int[int] squares;
> }
>
> void main()
> {
> auto squares = [0 : 0, 1 : 1];
>
> C c = new C();
> c.squares = squares;
>
> writeln(c.squares is squares); // true
>
> squares = null;
> squares[10] = 100;
> writeln(c.squares is squares); // false
> }
>
> If the runtime used the same underlying memory, the second writeln()
would print true, right?
> So if I am correct, a new AA is allocated.
Probably depends on the current implementation. If you are using an
associative array you are going to be allocating at least a little.
If you used an associative array backed by two arrays you could allocate
and reuse memory when null is assigned. It would also be able to keep its
insertion order.
Re: Hash Tables in D
On Wednesday, 6 January 2016 at 12:19:45 UTC, Jacob Carlborg
wrote:
On 2016-01-05 15:44, Minas Mina wrote:
It won't, but to use it again you need to allocate a new one
(If I'm not
mistaken).
Not explicitly. I don't know if the runtime allocates a new
one. This works:
void main()
{
auto foo = ["foo" : 1];
foo = null;
foo["bar"] = 2;
assert(foo["bar"] == 2);
}
I believe it does, check out this example:
import std.stdio;
class C
{
int[int] squares;
}
void main()
{
auto squares = [0 : 0, 1 : 1];
C c = new C();
c.squares = squares;
writeln(c.squares is squares); // true
squares = null;
squares[10] = 100;
writeln(c.squares is squares); // false
}
If the runtime used the same underlying memory, the second
writeln() would print true, right?
So if I am correct, a new AA is allocated.
Re: Hash Tables in D
On 2016-01-05 15:44, Minas Mina wrote:
It won't, but to use it again you need to allocate a new one (If I'm not
mistaken).
Not explicitly. I don't know if the runtime allocates a new one. This works:
void main()
{
auto foo = ["foo" : 1];
foo = null;
foo["bar"] = 2;
assert(foo["bar"] == 2);
}
--
/Jacob Carlborg
Re: Hash Tables in D
On Tuesday, 5 January 2016 at 13:36:48 UTC, Jacob Carlborg wrote: On 2016-01-05 11:19, Minas Mina wrote: I haven't found a way to clear an AA without allocating though. (Creating a new one doesn't count). Set it to "null", or will that allocate a new one? It won't, but to use it again you need to allocate a new one (If I'm not mistaken).
Re: Hash Tables in D
On 2016-01-05 11:19, Minas Mina wrote: I haven't found a way to clear an AA without allocating though. (Creating a new one doesn't count). Set it to "null", or will that allocate a new one? -- /Jacob Carlborg
Re: Hash Tables in D
On Monday, 4 January 2016 at 19:58:03 UTC, Martin Nowak wrote: On 01/04/2016 09:06 AM, Bastiaan Veelo wrote: This would be a bug (segfault on my machine): foreach (key; aa.byKey) aa.remove(key); Note that, in this example, there is no need to remove every element separately, you can also just do Sorry my mistake, I never use aa.keys (instead of aa.byKey) b/c it allocates. So it's still sort of a bug to recommend people allocating an array ;). I haven't found a way to clear an AA without allocating though. (Creating a new one doesn't count).
Re: Hash Tables in D
On 01/04/2016 09:06 AM, Bastiaan Veelo wrote: > > This would be a bug (segfault on my machine): > >> foreach (key; aa.byKey) >> aa.remove(key); > > Note that, in this example, there is no need to remove every element > separately, you can also just do Sorry my mistake, I never use aa.keys (instead of aa.byKey) b/c it allocates. So it's still sort of a bug to recommend people allocating an array ;).
Re: Hash Tables in D
On Monday, 4 January 2016 at 07:09:30 UTC, Minas Mina wrote:
On Sunday, 3 January 2016 at 19:29:05 UTC, Martin Nowak wrote:
There is a bug.
You should never do this b/c of iterator/range invalidation.
foreach (key; aa.keys)
aa.remove(key);
The reference states that keys: "Returns dynamic array, the
elements of which are the keys in the associative array".
Isn't the array newly allocated?
Hi,
You are right:
void main()
{
import std.stdio;
int[int] aa;
foreach (i; 0..9)
aa[i] = i * 10;
writeln(aa); // [0:0, 6:60, 7:70, 2:20, 3:30, 1:10, 8:80,
5:50, 4:40]
foreach (key; aa.keys)
aa.remove(key);
writeln(aa); // []
}
This would be a bug (segfault on my machine):
foreach (key; aa.byKey)
aa.remove(key);
Note that, in this example, there is no need to remove every
element separately, you can also just do
void main()
{
import std.stdio;
int[int] aa;
foreach (i; 0..9)
aa[i] = i * 10;
writeln(aa); // [0:0, 6:60, 7:70, 2:20, 3:30, 1:10, 8:80,
5:50, 4:40]
aa = null;
writeln(aa); // []
}
Bastiaan.
Re: Hash Tables in D
On Sunday, 3 January 2016 at 19:29:05 UTC, Martin Nowak wrote: On 01/01/2016 04:27 PM, Minas Mina wrote: On Friday, 1 January 2016 at 13:59:35 UTC, Walter Bright wrote: http://minas-mina.com/2016/01/01/associative-arrays/ https://www.reddit.com/r/programming/comments/3z03ji/hash_tables_in_the_d_programming_language/ Thanks for sharing this. I am the author. :) There is a bug. You should never do this b/c of iterator/range invalidation. foreach (key; aa.keys) aa.remove(key); The reference states that keys: "Returns dynamic array, the elements of which are the keys in the associative array". Isn't the array newly allocated?
Re: Hash Tables in D
On 01/01/2016 04:27 PM, Minas Mina wrote: > On Friday, 1 January 2016 at 13:59:35 UTC, Walter Bright wrote: >> http://minas-mina.com/2016/01/01/associative-arrays/ >> >> https://www.reddit.com/r/programming/comments/3z03ji/hash_tables_in_the_d_programming_language/ >> > > Thanks for sharing this. I am the author. :) There is a bug. You should never do this b/c of iterator/range invalidation. foreach (key; aa.keys) aa.remove(key);
Re: Hash Tables in D
On 1/1/2016 7:27 AM, Minas Mina wrote: On Friday, 1 January 2016 at 13:59:35 UTC, Walter Bright wrote: http://minas-mina.com/2016/01/01/associative-arrays/ https://www.reddit.com/r/programming/comments/3z03ji/hash_tables_in_the_d_programming_language/ Thanks for sharing this. I am the author. :) You're welcome, and thanks for writing the nice article.
Re: Hash Tables in D
On Friday, 1 January 2016 at 13:59:35 UTC, Walter Bright wrote: http://minas-mina.com/2016/01/01/associative-arrays/ https://www.reddit.com/r/programming/comments/3z03ji/hash_tables_in_the_d_programming_language/ Thanks for sharing this. I am the author. :)
