Re: I hate new DUB config format

[Daniel N via Digitalmars-d]

On Monday, 30 November 2015 at 20:42:23 UTC, Suliman wrote:
Should we try to implement yet another language for writing 
building config? Maybe we should use any of existence language 
that may be very good for it, like Red. It have very small foot 
prints so it can be easy to embeded to build system.


-The only winning choice is not to choose.

I'm kinda spoiled by rdmd, I honestly don't see why I should go 
back to using config files again, pragma(lib) already exists and 
one could extend it with UDA:s for more advanced use-cases. Well, 
never mind. Most ppl seem happy with DUB:s approach though, so I 
guess it's just me.

And here's another interesting algorithm/structure: Randomized Slide to Front

[Andrei Alexandrescu via Digitalmars-d]

Now that we got talking about searching in arrays, allow me to also 
share an idea I've had a short while ago.


(Again, we're in the "I'd prefer to use an array if at all possible" 
mindset. So let's see how we can help searching an array with as little 
work as possible.)


One well-known search strategy is "Bring to front" (described by Knuth 
in TAoCP). A BtF-organized linear data structure is searched with the 
classic linear algorithm. The difference is what happens after the 
search: whenever the search is successful, the found element is brought 
to the front of the structure. If we're looking most often for a handful 
of elements, in time these will be near the front of the searched structure.


For a linked list, bringing an element to the front is O(1) (just rewire 
the pointers). For an array, things are not so pleasant - rotating the 
found element to the front of the array is O(n).


So let's see how we can implement a successful BtF for arrays.

The first idea is to just swap the found element with the first element 
of the array. That's O(1) but has many disadvantages - if you search 
e.g. for two elements, they'll compete for the front of the array and 
they'll go back and forth without making progress.


Another idea is to just swap the found element with the one just before 
it. The logic is, each successful find will shift the element closer to 
the front, in a bubble sort manner. In time, the frequently searched 
elements will slowly creep toward the front. The resulting performance 
is not appealing - you need O(n) searches to bring a given element to 
the front, for a total of O(n * n) steps spent in the n searches. Meh.


So let's improve on that: whenever an element is found in position k, 
pick a random number i in the range 0, 1, 2, ..., k inclusive. Then swap 
the array elements at indexes i and k. This is the Randomized Slide to 
Front strategy.


With RStF, worst case search time remains O(n), as is the unsuccessful 
search. However, frequently searched elements migrate quickly to the 
front - it only takes O(log n) searches to bring a given value at the 
front of the array.


Insertion and removal are both a sweet O(1), owing to the light 
structuring: to insert just append the element (and perhaps swap it in a 
random position of the array to prime searching for it). Removal by 
position simply swaps the last element into the position to be removed 
and then reduces the size of the array.


So the RStF is suitable in all cases where BtF would be recommended, but 
allows an array layout without considerable penalty.


Related work: Theodoulos Garefalakis' Master's thesis "A Family of 
Randomized Algorithms for List Accessing" describes Markov Move to 
Front, which brings the searched element to front according to a Markov 
chain schedule; and also Randomized Move to Front, which decides whether 
a found element is brought to front depending on a random choice. These 
approaches are similar in that they both use randomization, but 
different because neither has good complexity on array storage.



Andrei

[Issue 15391] Problems loading libcurl.so and running datetime unittest on NixOS package build

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15391

Jonathan M Davis  changed:

   What|Removed |Added

 CC||issues.dl...@jmdavisprog.co
   ||m

--- Comment #4 from Jonathan M Davis  ---
What are you doing differently from normal that makes it so that the normal
path for the time zone files doesn't work?

--

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 4:33 PM, Andrei Alexandrescu wrote:
[snip]

I just posted to reddit: 
https://www.reddit.com/r/programming/comments/3uwp42/its_my_birthday_so_heres_some_cake_for_thought/


Andrei

Re: This Week in D

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 20:07:10 UTC, Adam D. Ruppe wrote:

I'll change it to "thread" on the front page.


:-)


On Monday, 30 November 2015 at 21:47:21 UTC, ketmar wrote:
"professional". this means "boring, uninteresting, written for 
witless idiots without sense of humor". the worst think we can 
do is start attracting such kind of people.


You have 3 seconds to convince a random visitor that the site is 
worth his/her time. If I am looking for a tool the last thing I 
want is to try to download something from an emotional boy scouts 
club. But then again, may you are right. Maybe the forums need 
more boy scouts.

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:

What about when element i is matched, swap it with the (i/2)'th element?


Randomization is essential - without it you have thrashing if you search 
for 2 elements in alternation. -- Andrei

Re: This Week in D

[ketmar via Digitalmars-d]

On Monday, 30 November 2015 at 14:07:03 UTC, Ola Fosheim Grøstad 
wrote:

therefore be a good idea to keep the front page professional.


"professional". this means "boring, uninteresting, written for 
witless idiots without sense of humor". the worst think we can do 
is start attracting such kind of people.

Re: extern(C++, NS)

[Daniel Murphy via Digitalmars-d]

On 30/11/2015 10:42 PM, Manu via Digitalmars-d wrote:
>

Exactly, the D module system would still be in place. Assuming they
were in defferent modules, then the D module system would keep them
out of conflict naturally, with rules identical to the normal D rules.
I imagined this; C++ namespace is for mangling, D module is for
scoping. That's not how it seems to be, so my intuition was dead
wrong, but my weekend's experience has convinced me it would be better
how I initially intuited. Thing is, we're presenting a C++ API to D,
so we want to present it in D's terms, that is, the API is distributed
among D modules in a way that makes sense to a D user. I don't want to
present the API in C++ terms, and it's not even practical; stuffing
the entire C++ API into a single D module is crazy. In the cases I'm
interested in, the C++ API is possibly larger than the entire D
codebase that's attached to it.



You're not the only one who thought it should be that way.

Re: JSON5 support for std.json

[Chris Wright via Digitalmars-d]

On Mon, 30 Nov 2015 20:42:20 +, Jack Stouffer wrote:
> JSON5 is also just a terrible idea. There is a very good reason why JSON
> does not have comments
> https://plus.google.com/+DouglasCrockfordEsq/posts/RK8qyGVaGSr and why
> it's strict. Data formats should have data, not anything else.

I fully understand and sympathize with desires for simple formats for 
data generated by a program to be read by a program. JSON is just fine 
for REST interfaces. It's great as a storage format for document 
databases. I'm not advocating for JSON5 there.

But JSON is also used for human-edited configuration files.

Configuration files should allow for comments. I poke about /etc and see 
that nearly every file there has copious comments detailing which fields 
exist, what sorts of values are allowed, the effects that field has, what 
the default values are, and whether you need to coordinate values between 
them. I've probably used those comments several hundred times, and I'd 
spend many hours paging through Google and asking questions on 
stackoverflow if they didn't exist.

JSON forbids comments, which is less than ideal. But Ruby's JSON parser 
allows comments, as does Newtonsoft JSON.NET.

If a human is going to edit a document, it should ideally be easy to edit 
it. It would be friendly, for instance, to allow trailing commas, because 
that's one less thing that a human has to worry about. Java's org.json 
library, which is linked from and has its documentation hosted at 
json.org, allows trailing commas. Newtonsoft JSON.NET does likewise.

It would be friendlier to the fingers to be able to omit quotes on simple 
object keys since it's less typing and no less clarity. Many strings 
contain double quotes, so it would be nice to allow single-quoted 
strings. org.json allows single-quoted strings. JSON.NET allows unquoted 
object keys and single-quoted strings.

[Issue 15391] Problems loading libcurl.so and running datetime unittest on NixOS package build

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15391

Martin Nowak  changed:

   What|Removed |Added

 CC||c...@dawg.eu

--- Comment #5 from Martin Nowak  ---
(In reply to Thomas Mader from comment #3)
> I was able to hack around the issue by patching the curl.d sourcefile.
> 
>   #Ugly hack so the dlopen call has a chance to succeed.
>   substituteInPlace src/phobos/std/net/curl.d --replace libcurl.so
> ${curl}/lib/libcurl.so
> 
> 
> That's in the package description for the dmd package on NixOS. That's
> necessary because in NixOS every package is stored in isolation to
> everything else.
> So libcurl on my system resides in
> /nix/store/v5a69m1b823zm1yy8yvhrd2zi2w385b1-curl-7.44.0/lib/libcurl.so.

Maybe try to  LD_LIBRARY_PATH instead?
As mentioned here https://dlang.org/changelog/2.069.0.html#curl-dynamic-loading
you can also link against libcurl (make sure to use no-as-needed), then the
symbols will get loaded from your executable.

--

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[deadalnix via Digitalmars-d]

On Monday, 30 November 2015 at 21:50:09 UTC, Andrei Alexandrescu 
wrote:

On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
What about when element i is matched, swap it with the 
(i/2)'th element?


Randomization is essential - without it you have thrashing if 
you search for 2 elements in alternation. -- Andrei


You'd end up swaping the 2 element in front, but keep them both 
in front, so that sounds like it would have the same behavior as 
the randomized algorithm.


Where it gets hairy, is when you access 2 elements in the array 
that would swap each other without getting in the front (because 
they are at 2n and 2n + 1 with n big).

Re: I hate new DUB config format

[Atila Neves via Digitalmars-d]

On Monday, 30 November 2015 at 20:42:23 UTC, Suliman wrote:
Should we try to implement yet another language for writing 
building config? Maybe we should use any of existence language 
that may be very good for it, like Red. It have very small foot 
prints so it can be easy to embeded to build system.


I really don't think so. There are plenty of perfectly good 
languages available, D being one of them. The other ones you can 
write reggae builds in are Python, Ruby, Javascript and Lua.


Atila

Re: An interesting data structure with search time O(sqrt n)

[H. S. Teoh via Digitalmars-d]

On Mon, Nov 30, 2015 at 03:57:24PM -0500, Andrei Alexandrescu via Digitalmars-d 
wrote:
> On 11/30/15 3:20 PM, H. S. Teoh via Digitalmars-d wrote:
> >On Mon, Nov 30, 2015 at 03:13:11PM -0500, Andrei Alexandrescu via 
> >Digitalmars-d wrote:
> >>Okasaki's book is a continued inspiration of data structures and
> >>algorithms.
> >>
> >>I was thinking along the following lines: typical collections are
> >>searchable in linear time. Then we have highly structured
> >>collections that feature logarithmic search time. But there seems to
> >>be nothing in between. So I was thinking, what would be a data
> >>structure that allows O(sqrt n) search times?
> >>
> >>After a little tinkering, here's what I came up with.
> >
> >Interesting indeed.
> >
> >It leaves me wondering, though, what's the point of having an O(sqrt
> >n) collection? What are the advantages?  Why would I use this
> >structure instead of, say, a traditional array heap with O(log n)
> >search time?
> 
> (Heaps offer only linear search time. You may take advantage of the
> heap structure to skip portions of the array, but on average and in
> the worst case the search is still O(n). So I assume you meant "sorted
> array or one of the classic search trees".)

Right, I wrote that without thinking. :-P


> The motivation starts with a desire to use arrays as the fundamental
> layout.  There have been many trends in computing as of late, among
> which: cache hierarchies are here to stay and contiguous layout is
> preferable.
> 
> The short of it is, arrays are king. No two ways about it - following
> pointers is a losing strategy when there's an alternative. A variety
> of new data structures (Clojure's arrays, heaps with tombstones) avoid
> classic pointer-based data structures in favor of adding structure on
> top of arrays.

I'm not so sure about that. At the micro level, yes, following pointers
for a tree / graph / etc., that could easily fit in a small/medium sized
array is a losing strategy, due to cache misses, hardware prefetchers,
etc.. When you're dealing with larger amounts of data, though, things
become less clear-cut. If your array size is on the order of MB's or
GB's, pointers start looking a lot more attractive. IMO in the long run
what will win is data structures that use tree or pointer based
implementations in the large scale, but built on cache-friendly
array-based structures below a certain level of granularity.

I agree with you, though, that array-based structures of intermediate
big-O complexities are very interesting. If you can come up with an
array structure that has the same complexity for all common operations,
that could be useful as a quick-fix drop in solution in cases where top
performance isn't required, but you'd like something better than O(n)
array scanning.


T

-- 
Philosophy: how to make a career out of daydreaming.

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 4:58 PM, Steven Schveighoffer wrote:

On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:

On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:

What about when element i is matched, swap it with the (i/2)'th element?


Randomization is essential - without it you have thrashing if you search
for 2 elements in alternation. -- Andrei



What about selecting a random element in 0..k/2 instead of 0..k-1?


I think complexity would stay the same. Choosing a tighter range puts a 
greater weight on the last search than on recent searches.


One thing I like is that I choose 0..k, not 0..k-1, which means it's 
possible that the element stays put (no change in position). That 
reduces thrashing for the top (most frequently searched) few elements.



andrei

Re: Is there anyone willing to do the videos 18sex website?

[Suliman via Digitalmars-d-announce]

On Monday, 30 November 2015 at 20:51:01 UTC, mcss wrote:
Thanks to a friend's attention, but in our country is not 
allowed to do this type of website, belonging to the crime, I 
now have a headache this thing! Do you have any good ideas?


Maybe to add here some analog of chaturbate with programmers 
thematic?

Re: I hate new DUB config format

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 20:42:23 UTC, Suliman wrote:
Should we try to implement yet another language for writing 
building config?


No, I wasn't really talking about a build system for D, more like 
a hypothetic generic distributed build system for all languages. 
But I've read that Google uses a distributed build system for 
their big C++ applications. So people are working on such 
solutions already.


Maybe we should use any of existence language that may be very 
good for it, like Red. It have very small foot prints so it can 
be easy to embeded to build system.


I've never heard of Red, do you have a link?

Re: extern(C++, NS)

[Walter Bright via Digitalmars-d]

On 11/30/2015 12:47 PM, Ola Fosheim Grøstad wrote:

[...]


Summary: if the C++ declarations change then the D ones that interface to it 
have to change, too.


I'd have to say that's a given.

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[H. S. Teoh via Digitalmars-d]

On Mon, Nov 30, 2015 at 04:58:16PM -0500, Steven Schveighoffer via 
Digitalmars-d wrote:
> On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:
> >On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
> >>What about when element i is matched, swap it with the (i/2)'th element?
> >
> >Randomization is essential - without it you have thrashing if you
> >search for 2 elements in alternation. -- Andrei
> >
> 
> What about selecting a random element in 0..k/2 instead of 0..k-1?
[...]

Or selecting the (i/k)'th element for k = uniform(1..i)?


T

-- 
People walk. Computers run.

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 4:55 PM, deadalnix wrote:

I guess randomizing would avoid hitting pathological cases too often,
but would converge more slowly ?


That's it. Problem is with deterministic approaches pathological cases 
are easy to hit and relatively common. -- Andrei

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 4:53 PM, H. S. Teoh via Digitalmars-d wrote:

On Mon, Nov 30, 2015 at 01:41:12PM -0800, H. S. Teoh via Digitalmars-d wrote:
[...]

What about when element i is matched, swap it with the (i/2)'th
element?

Then it will take just log(n) searches to bring it to the front of the
array, but it won't (immediately) compete with whatever's currently
the most popular item in the array. Furthermore, when it does compete
with it, it will already have been moved closer to the front of the
array, so the previous most-popular element won't be pushed far back
into the deep recesses of the array, but remain close to the front
where it will be quickly found.


In fact, it's probably provable that if there are 2 most popular items
in the array, they will eventually migrate to the 1st two positions of
the array. Not so sure about the case of n most popular items for n>2,
as position 3 is a kind of odd case where it gets displaced only by
elements from indices that aren't a power of 2, but it would seem at a
cursory glance that the 3 most popular items would tend to settle around
the first 4 elements of the array.

Hmm... it seems that in the worst case (the most popular n items all lie
precisely at indices of the form 2^j) the most popular items will end up
within the first 2^n positions of the array. Not sure how to compute the
average case; intuitively at least it seems that it should lie somewhere
between the first n positions and the first 2^n positions.


With RStF it's easy to prove (e.g. by reductio ad absurdum) that if you 
search only for k items out of n, they will end up in the top k 
positions of the array. Then they'll churn there :o). The key to the 
proof is that in the stationary state no element migrates in our out of 
the top k slots. I think it would be difficult to achieve this property 
with a deterministic approach.


The more interesting question would be what the element distribution is 
if both elements and searches are Gaussian-distributed (probably a 
frequent case in practice).



Andrei

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[H. S. Teoh via Digitalmars-d]

On Mon, Nov 30, 2015 at 01:41:12PM -0800, H. S. Teoh via Digitalmars-d wrote:
[...]
> What about when element i is matched, swap it with the (i/2)'th
> element?
> 
> Then it will take just log(n) searches to bring it to the front of the
> array, but it won't (immediately) compete with whatever's currently
> the most popular item in the array. Furthermore, when it does compete
> with it, it will already have been moved closer to the front of the
> array, so the previous most-popular element won't be pushed far back
> into the deep recesses of the array, but remain close to the front
> where it will be quickly found.

In fact, it's probably provable that if there are 2 most popular items
in the array, they will eventually migrate to the 1st two positions of
the array. Not so sure about the case of n most popular items for n>2,
as position 3 is a kind of odd case where it gets displaced only by
elements from indices that aren't a power of 2, but it would seem at a
cursory glance that the 3 most popular items would tend to settle around
the first 4 elements of the array.

Hmm... it seems that in the worst case (the most popular n items all lie
precisely at indices of the form 2^j) the most popular items will end up
within the first 2^n positions of the array. Not sure how to compute the
average case; intuitively at least it seems that it should lie somewhere
between the first n positions and the first 2^n positions.


T

-- 
Любишь кататься - люби и саночки возить. 

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[H. S. Teoh via Digitalmars-d]

On Mon, Nov 30, 2015 at 04:33:27PM -0500, Andrei Alexandrescu via Digitalmars-d 
wrote:
[...]
> One well-known search strategy is "Bring to front" (described by Knuth
> in TAoCP). A BtF-organized linear data structure is searched with the
> classic linear algorithm. The difference is what happens after the
> search: whenever the search is successful, the found element is
> brought to the front of the structure. If we're looking most often for
> a handful of elements, in time these will be near the front of the
> searched structure.
[...]
> So let's see how we can implement a successful BtF for arrays.
> 
> The first idea is to just swap the found element with the first
> element of the array. That's O(1) but has many disadvantages - if you
> search e.g. for two elements, they'll compete for the front of the
> array and they'll go back and forth without making progress.
> 
> Another idea is to just swap the found element with the one just
> before it.  The logic is, each successful find will shift the element
> closer to the front, in a bubble sort manner. In time, the frequently
> searched elements will slowly creep toward the front. The resulting
> performance is not appealing - you need O(n) searches to bring a given
> element to the front, for a total of O(n * n) steps spent in the n
> searches. Meh.
> 
> So let's improve on that: whenever an element is found in position k,
> pick a random number i in the range 0, 1, 2, ..., k inclusive. Then
> swap the array elements at indexes i and k. This is the Randomized
> Slide to Front strategy.

What about when element i is matched, swap it with the (i/2)'th element?

Then it will take just log(n) searches to bring it to the front of the
array, but it won't (immediately) compete with whatever's currently the
most popular item in the array. Furthermore, when it does compete with
it, it will already have been moved closer to the front of the array, so
the previous most-popular element won't be pushed far back into the deep
recesses of the array, but remain close to the front where it will be
quickly found.

More generally, you could pick the (i/k)'th element for swapping when
you've matched an element, with k being a constant, chosen parameter.
You may be able to optimize for certain use cases (e.g., if you knew
beforehand the average number of "popular" elements) by choosing an
appropriate value of k.


T

-- 
Nobody is perfect.  I am Nobody. -- pepoluan, GKC forum

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[deadalnix via Digitalmars-d]

On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu 
wrote:
Now that we got talking about searching in arrays, allow me to 
also share an idea I've had a short while ago.


(Again, we're in the "I'd prefer to use an array if at all 
possible" mindset. So let's see how we can help searching an 
array with as little work as possible.)


One well-known search strategy is "Bring to front" (described 
by Knuth in TAoCP). A BtF-organized linear data structure is 
searched with the classic linear algorithm. The difference is 
what happens after the search: whenever the search is 
successful, the found element is brought to the front of the 
structure. If we're looking most often for a handful of 
elements, in time these will be near the front of the searched 
structure.


For a linked list, bringing an element to the front is O(1) 
(just rewire the pointers). For an array, things are not so 
pleasant - rotating the found element to the front of the array 
is O(n).


So let's see how we can implement a successful BtF for arrays.

The first idea is to just swap the found element with the first 
element of the array. That's O(1) but has many disadvantages - 
if you search e.g. for two elements, they'll compete for the 
front of the array and they'll go back and forth without making 
progress.


Another idea is to just swap the found element with the one 
just before it. The logic is, each successful find will shift 
the element closer to the front, in a bubble sort manner. In 
time, the frequently searched elements will slowly creep toward 
the front. The resulting performance is not appealing - you 
need O(n) searches to bring a given element to the front, for a 
total of O(n * n) steps spent in the n searches. Meh.


So let's improve on that: whenever an element is found in 
position k, pick a random number i in the range 0, 1, 2, ..., k 
inclusive. Then swap the array elements at indexes i and k. 
This is the Randomized Slide to Front strategy.


With RStF, worst case search time remains O(n), as is the 
unsuccessful search. However, frequently searched elements 
migrate quickly to the front - it only takes O(log n) searches 
to bring a given value at the front of the array.


Insertion and removal are both a sweet O(1), owing to the light 
structuring: to insert just append the element (and perhaps 
swap it in a random position of the array to prime searching 
for it). Removal by position simply swaps the last element into 
the position to be removed and then reduces the size of the 
array.


So the RStF is suitable in all cases where BtF would be 
recommended, but allows an array layout without considerable 
penalty.


Related work: Theodoulos Garefalakis' Master's thesis "A Family 
of Randomized Algorithms for List Accessing" describes Markov 
Move to Front, which brings the searched element to front 
according to a Markov chain schedule; and also Randomized Move 
to Front, which decides whether a found element is brought to 
front depending on a random choice. These approaches are 
similar in that they both use randomization, but different 
because neither has good complexity on array storage.



Andrei


What is the advantage compared to let's say a ringbuffer ? On 
find you can put the element to the front, and swap the old 
element with the new element ?


I guess randomizing would avoid hitting pathological cases too 
often, but would converge more slowly ?

Re: extern(C++, NS)

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 21:42:19 UTC, Walter Bright wrote:

On 11/30/2015 12:47 PM, Ola Fosheim Grøstad wrote:

[...]


Summary: if the C++ declarations change then the D ones that 
interface to it have to change, too.


I'd have to say that's a given.


It might be a given, but as pure C++11 libraries become more 
common people will need a way to deal with inlined namespaces in 
a way that isn't annoying. And if the changes does not show up in 
the mangling, then it won't be caught at link-time either. We'll 
see...

Re: And here's another interesting algorithm/structure: Randomized Slide to Front

[Steven Schveighoffer via Digitalmars-d]

On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:

On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:

What about when element i is matched, swap it with the (i/2)'th element?


Randomization is essential - without it you have thrashing if you search
for 2 elements in alternation. -- Andrei



What about selecting a random element in 0..k/2 instead of 0..k-1?

-Steve

having problem with `std.algorithm.each`

[ref2401 via Digitalmars-d-learn]

It seems like `std.algorithm.each` is not executed in the example 
below.

Could anyone tell why?
Thank you.


import std.algorithm;

void main(string[] args) {
int[] arr = [1, 2, 3, 4, 5];

arr.each!((ref e) => {
writeln(e); // does not print
++e;
})();

writeln(arr); // prints [1, 2, 3, 4, 5]
}

Re: having problem with `std.algorithm.each`

[ref2401 via Digitalmars-d-learn]

DMD 2.069.1
OS Win8.1 Enterprise

Re: extern(C++, NS)

[deadalnix via Digitalmars-d]

On Monday, 30 November 2015 at 07:45:54 UTC, Walter Bright wrote:
Why not produce something similar to an overload set for C++ 
namespace ? An
error needs to be issued only if X or Y is duplicated, 
otherwise, this is fine.


Because I'd rather have symbol table lookups done in a 
consistent manner, rather than special casing it everywhere. 
The above behavior is completely consistent with how everything 
else works, because it uses the exact same code.


The proposed behavior is also not new (as per spec, alas it 
doesn't work in DMD), as it is the same as for multiple alias 
this.

Re: I hate new DUB config format

[Luis via Digitalmars-d]

On Sunday, 29 November 2015 at 17:25:04 UTC, Poyeyo wrote:


rust cargo -> rust manifest



rust cargo -> toml

vibe.d-example illustrating Dynamic Textual Web-Interface

[Nordlöw via Digitalmars-d-learn]

Can somebody please show a enlightening example of, so called,

"revamp of the REST interface generator"

added to release 0.7.26 at:

http://vibed.org/blog/posts/vibe-release-0.7.26

I want to use vibe.d to add a modern dynamic web-interface to my 
knowledge graph I'm currently developing.


More specifically I would like an interface that makes rich use 
of dynamic HTML. When the user changes the contents of a 
search/command-line text-field the client logic shall on the fly 
(after a certain delay) lookup related information with 
vibe.d-server and present the user with relevant hits or 
completions in a another part of page (HTML div-block).


Does anybody have a similar vibe.d-project to be inspired from, 
in this regard?

Re: extern(C++, NS)

[Kagamin via Digitalmars-d]

On Sunday, 29 November 2015 at 04:57:28 UTC, Walter Bright wrote:
We considered making them for mangling only, and rejected it as 
unworkable, because then two identical names in different 
namespaces could not be distinguished by the D symbol table 
system.


Didn't you show how two identical names can be distinguished with 
D symbol table system:


On Sunday, 29 November 2015 at 18:29:14 UTC, Walter Bright wrote:

file1.NS.X x;
file2.NS.Y y;


It also works the same for C bindings: they share (empty) 
namespace, but identical C declarations can be distinguished in D 
if they are in different modules. Maybe it's better to ignore C 
namespaces and rely on D module system instead?
Though I don't know why one would want to disallow access to a 
C++ namespace.

Re: Is D ready for quants?

[Dominikus Dittes Scherkl via Digitalmars-d]

On Monday, 30 November 2015 at 04:16:10 UTC, Saurabh Das wrote:
On Monday, 30 November 2015 at 04:06:07 UTC, Jack Stouffer 
wrote:
This sounds interesting! Would you be willing to write a blog 
post on your experiences with this, or even better give a talk 
a DConf ;)?


I definitely want to write about my experiences - but there is 
just too much happening currently. Hopefully in December when 
there's a bit of down-time.


Nothing we've done is revolutionary so I am unsure whether it's 
interesting enough content for a DConf talk.


I would consider it very interesting - much more than enough. I 
hope to hear more about it at DConf.

Re: Classes as enums in D?

[Marc Schütz via Digitalmars-d-learn]

On Monday, 30 November 2015 at 08:08:20 UTC, Meta wrote:

class WhiteKey
{
private immutable int halfStepsToNext;
private immutable int halfStepsToPrevious;

enum
{
A = new WhiteKey(2, 2),
B = new WhiteKey(2, 1),
C = new WhiteKey(1, 2),
D = new WhiteKey(2, 2),
E = new WhiteKey(2, 1),
F = new WhiteKey(1, 2),
G = new WhiteKey(2, 2),
}

private this(int halfStepsToPrevious, int halfStepsToNext)
{
this.halfStepsToPrevious = halfStepsToPrevious;
this.halfStepsToNext = halfStepsToNext;
}
}

However, you do NOT want to do this, as everywhere you use 
WhiteKey's members, a new object will be created. For example:


auto f = WhiteKey.A;
auto n = WhiteKey.A;

import std.stdio;
writeln(, " ", );



You're misinterpreting this:

enum X {
A = new Object,
B = new Object,
}

void main() {
import std.stdio;
writeln(cast(void*) X.A);
writeln(cast(void*) X.A);
}

# output:
470910
470910

You're print the address of `f` and `n` on the stack, not the 
reference they're pointing to.


But it's true that enums of mutable _arrays_ do create a new 
instance every time they're used:


enum X {
A = [1,2,3],
B = [4,5,6],
}

void main() {
import std.stdio;
writeln(X.A.ptr);
writeln(X.A.ptr);
}

# output:
7FD887F0E000
7FD887F0E010

Re: Collections question

[Tobias Pankrath via Digitalmars-d]

On Monday, 30 November 2015 at 16:06:43 UTC, Steven Schveighoffer 
wrote:

MyCollection!(int) c1;
auto c2 = c1;
c1 ~= 1;

assert(c2.contains(1)); // pass? fail?

BTW, I third Jonathan's and Timon's suggestion -- go with an 
external factory function. Use IFTI to its fullest!


-Steve


That should throw, because you're using an uninitialised 
reference (c1). It's the equivalent to:


Class C { .. }

C c1;
C c2 = c1;
c1.foo(); // call via nullptr

Or it needs to pass, but that's probably not worth it.

Re: Efficient binary search using two-way comparisons

[Andrei Alexandrescu via Digitalmars-d]

On 11/29/2015 04:13 PM, Enamex wrote:

On Saturday, 28 November 2015 at 20:04:11 UTC, Andrei Alexandrescu wrote:

While reading Okasaki's bool on persistent data structures, I found
(page 14) a reference to a nice idea applicable to binary search using
D's two-way "less than" comparisons.

https://issues.dlang.org/show_bug.cgi?id=15385

Any takers?


Andrei


Looks really simple. I could try? Though I'll probably come asking here
about contribution procedures and stuff (especially that I can't, not
possibly, compile Phobos or anything close to it with tests and such).


Xinok got ahead, but don't let that deter you. I'll post here other 
similar simple yet interesting tasks, and I encourage others to do the 
same. -- Andrei

Re: I hate new DUB config format

[ZombineDev via Digitalmars-d]

On Monday, 30 November 2015 at 15:41:39 UTC, Tourist wrote:

On Monday, 30 November 2015 at 15:12:13 UTC, Sönke Ludwig wrote:
The number of posts in this thread has multiple reasons, I'd 
argue that it's questionable to draw conclusions from that.


Don't fool yourself. You made a mistake. That's fine. Own and 
fix it. Trying to make it look good is only making everything 
worse.


Any idea in this group will have a few enthusiasts, but here 
you have the majority of the community complaining and the 
three leaders Walter, Andrei, Martin tell you clear as rain you 
are wrong. What and why are you arguing?


Also, you need to contrast this to the amount of posts that 
complained about JSON, or those that would have happened for a 
different format choice.


So let's add more. How does that logic work?

Do you have an answer to the comment that the file format is 
dead?


No he didn't make a mistake. He added a better alternative to 
JSON, because other people demanded. SDLang is very good format I 
prefer it to all other formats for this purpose. It is more 
readable than JSON and this ***all*** that matters.
I don't even know why people complain about it. No one forces 
them to use it.
The whole argument that you shouldn't use something, just because 
it is not popular is stupid. After all why are you even on this 
forum? D is not the most popular language. Other programming 
communities invent new DSLs everyday and this doesn't stop people 
from using those languages/libaries. Just look at the ruby 
ecosystem.

Re: I hate new DUB config format

[terchestor via Digitalmars-d]

On Monday, 30 November 2015 at 17:06:56 UTC, ZombineDev wrote:

On Monday, 30 November 2015 at 15:41:39 UTC, Tourist wrote:
On Monday, 30 November 2015 at 15:12:13 UTC, Sönke Ludwig 
wrote:
The number of posts in this thread has multiple reasons, I'd 
argue that it's questionable to draw conclusions from that.


Don't fool yourself. You made a mistake. That's fine. Own and 
fix it. Trying to make it look good is only making everything 
worse.


Any idea in this group will have a few enthusiasts, but here 
you have the majority of the community complaining and the 
three leaders Walter, Andrei, Martin tell you clear as rain 
you are wrong. What and why are you arguing?


Also, you need to contrast this to the amount of posts that 
complained about JSON, or those that would have happened for 
a different format choice.


So let's add more. How does that logic work?

Do you have an answer to the comment that the file format is 
dead?


No he didn't make a mistake. He added a better alternative to 
JSON, because other people demanded.


The poll 
http://www.easypolls.net/poll.html?p=565587f4e4b0b3955a59fb67 
shows right now that 70% of 98 voters DISILIKE SDL.



SDLang is very good format


Why does nobody use it then? Not even the peoples who introduced 
it use it.


I prefer it to all other formats for this purpose. It is more 
readable than JSON and this ***all*** that matters.


What is your largest SDL file? Please paste it so we can look for 
ourselves?


I don't even know why people complain about it. No one forces 
them to use it.


They complain because it's there and it should not be.

The whole argument that you shouldn't use something, just 
because it is not popular is stupid. After all why are you even 
on this forum? D is not the most popular language. Other 
programming communities invent new DSLs everyday and this 
doesn't stop people from using those languages/libaries. Just 
look at the ruby ecosystem.


Popularity is not the first argument.

Re: Collections question

[Steven Schveighoffer via Digitalmars-d]

On 11/30/15 11:21 AM, Tobias Pankrath wrote:

On Monday, 30 November 2015 at 16:06:43 UTC, Steven Schveighoffer wrote:

MyCollection!(int) c1;
auto c2 = c1;
c1 ~= 1;

assert(c2.contains(1)); // pass? fail?

BTW, I third Jonathan's and Timon's suggestion -- go with an external
factory function. Use IFTI to its fullest!


That should throw, because you're using an uninitialised reference (c1).
It's the equivalent to:

Class C { .. }

C c1;
C c2 = c1;
c1.foo(); // call via nullptr

Or it needs to pass, but that's probably not worth it.


It means such a collection won't operate in the same way that 
associative arrays do.


If that's the case, I'm OK with that.

Technically, a wrapper could be constructed that performed the "lazy 
creation".


But my point to Andrei was that the functions he suggests don't actually 
address the "oddity" of copying AAs. Addressing it, if it's done in the 
way you say, is as simple as not worrying about null pointers.


-Steve

Re: Is D ready for quants?

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/2015 05:12 AM, Dominikus Dittes Scherkl wrote:

On Monday, 30 November 2015 at 04:16:10 UTC, Saurabh Das wrote:

On Monday, 30 November 2015 at 04:06:07 UTC, Jack Stouffer wrote:

This sounds interesting! Would you be willing to write a blog post on
your experiences with this, or even better give a talk a DConf ;)?


I definitely want to write about my experiences - but there is just
too much happening currently. Hopefully in December when there's a bit
of down-time.

Nothing we've done is revolutionary so I am unsure whether it's
interesting enough content for a DConf talk.


I would consider it very interesting - much more than enough. I hope to
hear more about it at DConf.


Let me just say that Experience Reports have been a very successful 
topic at DConf. -- Andrei

Re: DUB, Platform specifications and dependencies

[Sönke Ludwig via Digitalmars-d-learn]

Am 24.11.2015 um 19:51 schrieb Zardoz:

Actually I'm trying to setup dub to not grab a dependency on Windows (
https://github.com/Zardoz89/DEDCPU-16/blob/master/dub.sdl ) :

name "dedcpu"
authors "Luis Panadero Guardeño"
targetType "none"
license "BSD 3-clause"
description "DCPU-16 tools"

subPackage {
   name "lem1802"
   description "Visual LEM1802 font editor"
   targetType "executable"
   targetName "lem1802"
   excludedSourceFiles "src/bconv.d"
   excludedSourceFiles "src/ddis.d"
   dependency "gtk-d:gtkd" version="~>3.2.0" platform="posix"
   libs "gtkd" platform="windows"
}

...

How ever, running dub on Windows (tested on two different machines),
ignores platform specification for gtk-d dependency . What I'm doing
wrong ?


Platform specifications are currently not supported for dependencies due 
to the way the dependency resolver works. However, it is possible to use 
platform specific configurations for this purpose:


name "dedcpu"
authors "Luis Panadero Guardeño"
targetType "none"
license "BSD 3-clause"
description "DCPU-16 tools"

subPackage {
   name "lem1802"
   description "Visual LEM1802 font editor"
   targetType "executable"
   targetName "lem1802"
   excludedSourceFiles "src/bconv.d"
   excludedSourceFiles "src/ddis.d"
   libs "gtkd" platform="windows"

   configuration "nogtk" {
  platforms "windows"
   }

   configuration "gtk" {
  platforms "posix"
  dependency "gtk-d:gtkd" version="~>3.2.0"
   }
}

[Issue 15378] dlang.org does not completely work with https:

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15378

Adam D. Ruppe  changed:

   What|Removed |Added

 CC||destructiona...@gmail.com

--- Comment #2 from Adam D. Ruppe  ---
The whole url bar showing as green is kinda rare, that signifies the extended
validation thing. My bank does it but no other site I go to does.

--

[Issue 15391] Deadlock in std.net.curl unittest in checkPhase of NixOS package build

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15391

--- Comment #2 from Thomas Mader  ---
Running the testsuite in the shell instead of inside the package creation
process gives me an Exception and the process deadlocks in the same place.
So the libcurl dependency cannot be resolved.

** FAIL debug64 std.net.curl
std.net.curl.CurlException@std/net/curl.d(3885): Failed to load curl, tried
"libcurl.so", "libcurl.so.4", "libcurl-gnutls.so.4", "libcurl-nss.so.4",
"libcurl.so.3".

--

Re: Collections question

[Steven Schveighoffer via Digitalmars-d]

On 11/27/15 3:14 PM, Andrei Alexandrescu wrote:

There's this oddity of built-in hash tables: a reference to a non-empty
hash table can be copied and then both references refer to the same hash
table object. However, if the hash table is null, copying the reference
won't track the same object later on.

Fast-forward to general collections. If we want to support things like
reference containers, clearly that oddity must be addressed. There are
two typical approaches:

1. Factory function:

struct MyCollection(T)
{
 static MyCollection make(U...)(auto ref U args);
 ...
}

So then client code is:

auto c1 = MyCollection!(int).make(1, 2, 3);
auto c2 = MyCollection!(int).make();
auto c3 = c2; // refers to the same collection as c2

2. The opCall trick:

struct MyCollection(T)
{
 static MyCollection opCall(U...)(auto ref U args);
 ...
}

with the client code:

auto c1 = MyCollection!(int)(1, 2, 3);
auto c2 = MyCollection!(int)();
auto c3 = c2; // refers to the same collection as c2

There's some experience in various libraries with both approaches. Which
would you prefer?


How do you prevent the AA behavior? In other words, what happens here:

MyCollection!(int) c1;
auto c2 = c1;
c1 ~= 1;

assert(c2.contains(1)); // pass? fail?

BTW, I third Jonathan's and Timon's suggestion -- go with an external 
factory function. Use IFTI to its fullest!


-Steve

Re: DateTime.opBinary

[Chris Wright via Digitalmars-d-learn]

On Mon, 30 Nov 2015 01:30:28 -0800, Jonathan M Davis via
Digitalmars-d-learn wrote:

> On Sunday, November 29, 2015 23:53:41 Chris Wright via
> Digitalmars-d-learn wrote:
>> Unfortunately, ddoc doesn't automatically cross-reference these for
>> you,
>> which results in confusion. (As if it weren't confusing enough to have
>> everything wrapped in templates with filters rather than simply using
>> const(Duration).)
> 
> Once TickDuration finally goes away, then functions like DateTime's
> opBinary can be simplified to just take Duration.
> 
> But until TickDuration and the few things that use it in their API have
> gone through the deprecation process, we're stuck with it in places like
> this.
> 
> - Jonathan M Davis

Or with explicit overloads, which would be easier to document and easier 
to read and as easy to maintain.

Re: JSON5 support for std.json

[Chris Wright via Digitalmars-d]

On Mon, 30 Nov 2015 03:40:12 +, Jack Stouffer wrote:

> On Monday, 30 November 2015 at 00:30:07 UTC, Chris Wright wrote:
>> I'm considering adding JSON5 support to std.json and want to know how
>> well this would be received.
> 
> Considering this is something that has apparently existed for more than
> three years and this is the first time I'm hearing of it, I have a hard
> time justifying it's inclusion into Phobos. I have never once heard of
> any project using JSON5 and googling it brings up one negative blog
> post, the HN post which is full of negative comments, and every other
> result are language bindings.
> 
> I have to agree with all the negativity, it seems like a poor idea and
> calling it "JSON" is inappropriate. Also, std.json is slated for
> deprecation.
> 
> If you want a JSON5 D parser, I'd say go ahead and throw it up on
> code.dlang.org. What would be much more beneficial IMO is a YAML parser
> based on the API of http://code.dlang.org/packages/std_data_json

JSON5 is pretty much just a codification of common relaxations to JSON 
parsers. For instance, a feature request for Newtonsoft JSON.NET (which 
is the most well known JSON library for .NET) to support JSON5 pretty 
much went "What's JSON5?" and then "Oh, we already support 90% of that".

The recent thread about DUB's config format would have been much more 
strongly in favor of JSON if std.json supported JSON5.

The reason to incorporate it into the standard library interpretation is 
because it's mostly identical to JSON, so sharing implementations is 
obvious.

[Issue 15391] Deadlock in std.net.curl unittest

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15391

--- Comment #1 from Thomas Mader  ---
I need to add that I try to run the unittests in the checkPhase of a package
build of NixOS and the network is restricted in this case I guess.
But the tests for std.socket were successful:

0.518s PASS debug64 std.socket

--

Re: I hate new DUB config format

[Tourist via Digitalmars-d]

On Monday, 30 November 2015 at 15:12:13 UTC, Sönke Ludwig wrote:
The number of posts in this thread has multiple reasons, I'd 
argue that it's questionable to draw conclusions from that.


Don't fool yourself. You made a mistake. That's fine. Own and fix 
it. Trying to make it look good is only making everything worse.


Any idea in this group will have a few enthusiasts, but here you 
have the majority of the community complaining and the three 
leaders Walter, Andrei, Martin tell you clear as rain you are 
wrong. What and why are you arguing?


Also, you need to contrast this to the amount of posts that 
complained about JSON, or those that would have happened for a 
different format choice.


So let's add more. How does that logic work?

Do you have an answer to the comment that the file format is dead?

Re: I hate new DUB config format

[Steven Schveighoffer via Digitalmars-d]

On 11/25/15 5:17 AM, Suliman wrote:

I think that using SDL format was big mistake. Not only I do not want to
spend time in learning yet another dead config format that now use only
one project -- DUB. In time when DUB used json it was not perfect, but
at last it was standard and everybody can read it.

Now when I come to code.dlang.org I can't simply do copy-past of
dependence. I need go to docs page, and read how to include it.

Also I do not see any projects that are migrate to SDL. Everybody
continue to use JSON. So please, return JSON back as default, or very
soon we will see that nobody do not submit packages to code.dlang.org
and nobody do not use DUB for their own projects.

Please vote about SDL config format
http://www.easypolls.net/poll.html?p=565587f4e4b0b3955a59fb67

If SDL will stay by default I will prefer to move to any other build
system or will downgrade to old version of DUB.


After reading the discussion here, I can safely conclude that I should 
have better spent the time picking lint out of my navel.


Killing thread...

-Steve

Re: I hate new DUB config format

[Sönke Ludwig via Digitalmars-d]

Am 27.11.2015 um 16:23 schrieb Walter Bright:

On 11/26/2015 11:08 PM, Sönke Ludwig wrote:

This looks like it's creeping towards inventing a new script programming
language. Adding loops, switch statements, functions, etc., can't be far
off. Before you get too far down this path, consider:


Actually, no! Conditionals and loops are the only constructs - switch
is a
possibility, but basically nothing else. There will also never be
variables,
just constants. There is a definitive limit, namely when it becomes
impossible
to reason about the code in a generic way, without "executing" it, so in
particular anything that would make it touring complete is a no-go - no
recursion, no loop flow control statements, no goto. In fact, there
are no
"statements" at all, these are all purely declarative "directives".


I would say to that: "famous last words". As Exhibit A, I submit 'static
if', which has been getting increasing pressure to augment with loops.


It's hard to make guarantees, true. But at least "static foreach" has 
always been a relatively obvious candidate, and at the same time there 
is a well defined limit in case of the package recipe format.



1. JSON has a superset programming language - Javascript - which has
conventional syntax rather than the DEP4 proposal for odd syntax like

 if dub-version="<0.9.24"

which I would strongly recommend against. And, we already have a
Javascript engine written in D:

 https://github.com/DigitalMars/DMDScript

2. D itself can be used as a scripting language (when # is the first
character in the source code). Having DUB use this might be quite
interesting.


On one hand that means that now you have to take care of security
issues (holes
in the scripting engine/compiler or DoS attacks of various sorts) when
you want
to use this on a server (code.dlang.org).


You have to deal with that even if just plain json or sdl. After all,
the implementation of those formats could be susceptible to buffer
overflow or DoS as well. But this is less likely with json, because
you'd be using a well-used json parser rather than your own sdl parser
that is only used for Dub.


The important difference is that a JSON/SDL parser has a vastly lower 
complexity than a scripting engine and, more importantly, the source 
file is just parsed in a linear fashion, without any arbitrary runtime 
execution. So when just parsing the format, making sure that the file is 
below a certain maximum size is enough to prevent typical DoS vectors.


For scripts, you'd at least have to be able to terminate after a certain 
time (but even with a relatively low timeout, say 5 seconds, it would be 
easy to bring the system down temporarily, by e.g. publishing a bunch of 
package versions at once). And if things like file system or network 
access are possible, the execution would realistically have to be moved 
to a sandbox (VM/chroot) environment to be safe.



(Yes I saw later that you use it in some

other projects, but does it see use outside of your own things?)


The current version of the sdlang-d package has been downloaded 83 times 
(DUB not counted) and there are GitHub issues opened by about 13 
different people, so it's definitely used for other projects, even if 
not yet hugely popular.



Javascript can only interact with its environment using the DOM. If Dub
presented its own DOM to the js engine, there isn't much the js code can
do other than go into an infinite loop, recursive overflow, or exploit a
buffer overflow.


This is where I'd see a similar problem to the "static foreach" one 
above. I'm pretty sure that people would start to ask for functions to 
access the file system, or to run arbitrary commands (which is fine on a 
local developer machine). It will be hard to argue against adding 
features that are so straight forward to implement.



Once there are big numbers of
packages, this could also mean that the hardware eventually needs to
be upgraded
when it would have done fine for a long time with a tiny declarative
parser.


I would think these problems have all been solved with Javascript, since
it is used so extensively. Javascript is also a lightweight scripting
language.


If the script is just a linear setup of the same fields as the current 
JSON/SDLang recipe then yes. But it's hard to predict what people will 
do with it. They might well go crazy and generate source code or other 
things that could take quite some time. It's just speculation, but the 
risk is there that this might considerably increase the load in the long 
run.



On the other hand, it's not possible with a script to make general
predictions
of how a package would behave, for example the script could select a
dependency
based on some environment variable or a file that is only defined on
the target
system.


That goes back to restricting the DOM.


True, but the pressure to add more power to the DOM will most likely be 
high.



Finally, it's always possible to switch from declarative to script

Re: Any D IDE on Mac OSX with debugging support?

[Bruno Medeiros via Digitalmars-d-learn]

On 16/11/2015 06:45, Vadim Lopatin wrote:

Hello,


Is there any IDE which allows debugging D apps on OSX?
I'm trying Mono-D, but getting error
"Debugger operation failed A syntax error in expression, near
'sizeof(void*)'"

GDB is installed using homebrew. Probably, something is wrong with my
gdb. When I'm trying to start debugging using console GDB interface - it
fails with message about unsigned application. Is there any instruction
how to get GDB working on OSX?

Code completion and symbol lookups neither do not work on Mono-D / OSX.
Does anyone managed to get it working?


Best regards,
 Vadim



Yes, DDT ( http://ddt-ide.github.io/ ) supports debugging on OSX, using 
GDB, but you have to install it with homebrew. If you have done it 
already, then it should work, but check this article as well: 
http://ntraft.com/installing-gdb-on-os-x-mavericks/



--
Bruno Medeiros
https://twitter.com/brunodomedeiros

[Issue 15391] Deadlock in std.net.curl unittest in checkPhase of NixOS package build

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15391

Thomas Mader  changed:

   What|Removed |Added

Summary|Deadlock in std.net.curl|Deadlock in std.net.curl
   |unittest|unittest in checkPhase of
   ||NixOS package build

--

grpc

[yawniek via Digitalmars-d]

would anyone be interested in doing the work for adding D / 
vibe.d to

https://github.com/grpc/grpc ?

we currently lack the manpower but would be able to sponsor it 
(or parts, depending on the effort needed).



grpc is probably going to be the dominant rpc system for building 
a microsrvices architecture. even though i prefer msgpack-rpc i 
think it would be very valuable in terms of connecting to e.g. GO 
services.

[Issue 15391] New: Deadlock in std.net.curl unittest

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15391

  Issue ID: 15391
   Summary: Deadlock in std.net.curl unittest
   Product: D
   Version: D2
  Hardware: x86_64
OS: Linux
Status: NEW
  Severity: normal
  Priority: P1
 Component: phobos
  Assignee: nob...@puremagic.com
  Reporter: thomas.ma...@gmail.com

I tried to run the unittests of phobos 2.069.1 but got the following deadlock
in test_runner while running the std.net.curl unittest:

(gdb) thread apply all bt

Thread 2 (Thread 0x71ce5700 (LWP 19261)):
#0  0x727a47dd in accept ()
   from
target:/nix/store/npfsi1d9ka8zwnxzn3sr08hbwvpapyk7-glibc-2.21/lib/libpthread.so.0
#1  0x7624eae4 in std.socket.Socket.accept() (this=0x77ef1700)
at std/socket.d:2855
#2  0x76f7fb8a in
std.net.curl.TestServer.loop(shared(std.socket.TcpSocket)) (
listener=0x77ef1700) at std/net/curl.d:213
#3  0x76fad46d in
std.concurrency._spawn!(void(shared(std.socket.TcpSocket)) function*,
shared(std.socket.TcpSocket))._spawn(bool, void(shared(std.socket.TcpSocket))
function*, shared(std.socket.TcpSocket)).exec() (this=0x77ef2100)
at std/concurrency.d:517
#4  0x775c903f in core.thread.Thread.run() (this=0x77eee500)
at src/core/thread.d:1351
#5  0x775c7f6c in thread_entryPoint (arg=0x60d850) at
src/core/thread.d:347
#6  0x7279d484 in start_thread ()
   from
target:/nix/store/npfsi1d9ka8zwnxzn3sr08hbwvpapyk7-glibc-2.21/lib/libpthread.so.0
#7  0x71dcd05d in clone ()
   from
target:/nix/store/npfsi1d9ka8zwnxzn3sr08hbwvpapyk7-glibc-2.21/lib/libc.so.6

Thread 1 (Thread 0x77ff25c0 (LWP 19260)):
#0  0x7279e65d in pthread_join ()
   from
target:/nix/store/npfsi1d9ka8zwnxzn3sr08hbwvpapyk7-glibc-2.21/lib/libpthread.so.0
#1  0x775c85b5 in core.thread.Thread.join(bool) (this=0x77eee500, 
rethrow=true) at src/core/thread.d:741
#2  0x775c9b7f in thread_joinAll () at src/core/thread.d:2283
#3  0x775eed0b in rt_term () at src/rt/dmain2.d:207
#4  0x775ef240 in rt.dmain2._d_run_main(int, char**, extern(C)
int(char[][]) function*).runAll() (this=0x7fffd990) at src/rt/dmain2.d:476
#5  0x775ef1c1 in rt.dmain2._d_run_main(int, char**, extern(C)
int(char[][]) function*).tryExec(scope void() delegate) (this=0x7fffd990,
dg=...)
at src/rt/dmain2.d:447
#6  0x775ef12b in _d_run_main (argc=2, argv=0x7fffda98, 
mainFunc=0x4017b0 ) at src/rt/dmain2.d:480
#7  0x00401988 in main ()
#8  0x71d06995 in __libc_start_main ()
   from
target:/nix/store/npfsi1d9ka8zwnxzn3sr08hbwvpapyk7-glibc-2.21/lib/libc.so.6
#9  0x004012e9 in _start ()

--

Re: I hate new DUB config format

[Russel Winder via Digitalmars-d]

On Sun, 2015-11-29 at 22:52 +, Ola Fosheim Gr via Digitalmars-d
wrote:
> 
[…]
> What is the advantage of having it in an imperative language, 
> though? Isn't a concurrent deductive language better and faster?

Project definitions should be declarative, definitely. Proejcts should
then have a default laying and naming scheme so that with convention
over configuration you need say nothing else. THis was the hope of
Maven and it chose XML. Then it became obvious that if you wanted even
a little non-standard behaviour you had to write you own Java coded
Maven plugin. So having a language which can offer a declarative DSL
and the ability to do a bit of imperative stuff if it is needed, you
get a good system. SCons and Gradle both do this: mostly declarative
with bits as needed.

> Then again, what is the point of every language inventing their 
> own eco system as an island...

Because, progress.

OK so there is the pissing contest of "my language makes a better build
system than any other" so every language has to have its own build
system. (Even Go switched from make to go.) However in doing this there
is often forward progress in build. Maven beats Ant. SCons and CMake
beat Make. etc., etc.

In the end though Lisp is the one true language, so we should all just
write in Lisp.

-- 
Russel.
=
Dr Russel Winder  t: +44 20 7585 2200   voip: sip:russel.win...@ekiga.net
41 Buckmaster Roadm: +44 7770 465 077   xmpp: rus...@winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder



signature.asc
Description: This is a digitally signed message part

Re: extern(C++, NS)

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 17:38:06 UTC, Walter Bright wrote:
It'd be worthwhile to learn how D's name lookup system works 
before declaring it lame and insufficient:


Nobody has said anything about lame. The issue is that you don't 
need to know of "version1" on the C++ side. One purpose is to use 
the "inline" as a switch, so that you can use macros to turn on 
and off different library subsets. "inline" is injected in front 
of namespaces that are to be accessible in the parent, and that 
injection can be done by a macro.


But on the D side you need to know of "version1" if D does not 
parse C++ headers. Which is a maintenance burden.

Re: This Week in D

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 19:01:59 UTC, Bubbasaur wrote:
Sorry if it seemed rude but the message wasn't for you and in 
fact I agree with you, it was a bit strange that mention on the 
newsletter.


Bubba.


*hugs*

Re: I hate new DUB config format

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 18:23:08 UTC, Chris wrote:
When will people understand that indentation should not be part 
of a language's syntax?


Where is that norm coming from? :-) I my experience YAML is a 
very visually clean format for configuration. I use it for 
configuration files for websites.


As I mentioned, if you don't want tab issues, then just restrict 
the grammar so you have uniform indentation.

Re: https everywhere!

[Kapps via Digitalmars-d-announce]

On Saturday, 28 November 2015 at 04:17:19 UTC, Martin Nowak wrote:
On Tuesday, 24 November 2015 at 08:48:58 UTC, Vladimir 
Panteleev wrote:
Sorry, I'm not going to pay for my own SSL certificate :) 
You'll either have to share, or wait until Let's Encrypt goes 
live and I get around to setting it up.


You could either get a free startssl certificate 
https://gist.github.com/mgedmin/7124635 or we try to reverse 
proxy through dlang.org/forum or so.


Letsencrypt goes into open beta in a few days 
(https://letsencrypt.org/2015/11/12/public-beta-timing.html). 
Could use that since it's free, allows subdomains (unlike 
StartSSL), easy setup, and people theoretically aren't doing 
anything on the site / forums where a theoretical early 
vulnerability is a huge concern.

Re: Gradle, Mave, etc. [was I hate new DUB config format]

[Russel Winder via Digitalmars-d]

On Sun, 2015-11-29 at 22:38 +, Paulo Pinto via Digitalmars-d wrote:
> 
[…]
> Only those that are required to use it for Android and suffer the 
> pain of slow builds yet to be fixed as announced on Google IO 
> 2015.
> 
> I have seen zero projects move to it, otherwise.

On the other hand I have seen none stay with Ant or Maven given the
option of Gradle. Those that stayed were told they didn't have an
option – for no good technical reason, just management "don't touch
anything" attitude.

> All our customers are on Ant and Maven.

Maven I can sort of live with but only on double pay. Ant is beyond the
pale in 2015. It was a late 1990s hack due to Make hatred.

> Personally I don't see any value on Gradle, besides having more 
> time to fetch coffee.

I see huge value in Gradle as a replacement for Maven (and Ant of
course). I have never seen the massive slow downs you intimate, for
projects I have seen with both Maven and Gradle builds, the Gradle
builds were a little slower, but the scripts were far, far easier to
maintain since al the imperative things were in the build scripts not
in additional Java plugins.

But this might be just a bikeshed issue. I have no intention of giving
up on Gradle and SCons, I am intransigent. :-)

-- 
Russel.
=
Dr Russel Winder  t: +44 20 7585 2200   voip: sip:russel.win...@ekiga.net
41 Buckmaster Roadm: +44 7770 465 077   xmpp: rus...@winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder



signature.asc
Description: This is a digitally signed message part

Re: Gradle, Mave, etc. [was I hate new DUB config format]

[CraigDillabaugh via Digitalmars-d]

On Monday, 30 November 2015 at 18:56:58 UTC, Russel Winder wrote:
On Sun, 2015-11-29 at 22:38 +, Paulo Pinto via 
Digitalmars-d wrote:





But this might be just a bikeshed issue. I have no intention of 
giving up on Gradle and SCons, I am intransigent. :-)


If it is a bikeshed issue then it will feel right at home in this 
thread.

Re: This Week in D

[Bubbasaur via Digitalmars-d]

On Monday, 30 November 2015 at 14:07:03 UTC, Ola Fosheim Grøstad 
wrote:
No drama, the sole purpose of the front page is to inform 
newcomers and it has much more impact than the forums. It would 
therefore be a good idea to keep the front page professional.


If there is not enough factual content for a weekly newsletter, 
then move to a bi-weekly.


Sorry if it seemed rude but the message wasn't for you and in 
fact I agree with you, it was a bit strange that mention on the 
newsletter.


Bubba.

[Issue 15391] Problems loading libcurl.so and running datetime unittest on NixOS package build

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15391

Thomas Mader  changed:

   What|Removed |Added

Summary|Deadlock in std.net.curl|Problems loading libcurl.so
   |unittest in checkPhase of   |and running datetime
   |NixOS package build |unittest on NixOS package
   ||build

--

Re: extern(C++, NS)

[Walter Bright via Digitalmars-d]

On 11/30/2015 3:42 AM, Manu via Digitalmars-d wrote:

That's not how it seems to be,


Are you still not understanding how name lookup works in D?

(You won't be the first. I explain it to people over and over, and nobody gets 
it. I have no idea why it is so hard to understand.)


C++ namespaces introduce scopes. The normal D lookup rules for scoped names 
applies. When names in C++ namespaces are mangled, they are mangled like C++ 
names would be, not like D names would be.


Lookup rules, apply one by one until found:

1. Look up in current scope.
2. Look up in imported scopes. Error if more than one is found.
3. Go up a level, and goto 1.

Re: I hate new DUB config format

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 17:18:50 UTC, terchestor wrote:
http://www.easypolls.net/poll.html?p=565587f4e4b0b3955a59fb67 
shows right now that 70% of 98 voters DISILIKE SDL.


Well, most people who didn't object probably didn't bother to 
vote... What about just hashing it out in YAML? It would look 
like this:



# this is a comment

name: my project
description: A little web service of mine.
authors:
- Peter Parker
- Spiderman
homepage: http://myproject.example.com
license: GPL-2.0
dependencies:
vibe-d: ~>0.7.23

Re: extern(C++, NS)

[Walter Bright via Digitalmars-d]

On 11/30/2015 3:42 AM, Manu via Digitalmars-d wrote:

Exactly, the D module system would still be in place. Assuming they
were in defferent modules, then the D module system would keep them
out of conflict naturally, with rules identical to the normal D rules.
I imagined this;


No need to imagine:

"Namespaces create a new named scope that is imported into its enclosing scope."

-- http://dlang.org/spec/attribute.html#namespace


C++ namespace is for mangling, D module is for
scoping. That's not how it seems to be, so my intuition was dead
wrong, but my weekend's experience has convinced me it would be better
how I initially intuited.


What about:

file1.NS.X x;
file2.NS.Y y;

?

Re: Collections question

[bitwise via Digitalmars-d]

On Saturday, 28 November 2015 at 13:39:35 UTC, Andrei 
Alexandrescu wrote:

On 11/28/15 1:59 AM, bitwise wrote:


Classes/real-ref-types dont act as you're describing, so why 
should
these fake struct wrapper ref things act this way? This will 
likely

achieve the exact opposite of what you're aiming for, by making
something that's supposed to act like a reference type have 
different

behaviour from D's built in ref types.


So what would work for you? -- Andrei


Sorry if that response seemed a tad flippant, but I have to be 
honest...I am completely against this design...to put it mildly.


I have my own containers to use, but on top of the fact that I 
would prefer something which is collaboratively maintained, I 
don't want to be forced to deal with, or support these 
"reference" containers, which will most likely happen if they get 
added to Phobos.


I'm really not sure where to begin tearing this idea apart. The 
principal I have a problem with is much more fundamental than 
this one decision. In general, there is a lot in D that is very 
hackish.


I understand that you don't want eager copying of containers, but 
when I way predictability, simplicity, clarity, and flexibility 
against that concern, there is no way I'm agreeing with you, when 
you can simply wrap a proper container in a RefCounted(T) or 
something. A class is a reference type, and a struct is a value 
type. If a user sees a struct, they should expect a value type 
which will copy on assign, and if they see a class, they should 
expect a reference. In D, the differentiation between value and 
reference types is clearly specified, and D users _should_ be, 
and should be expected to be, aware of it.


If you really want reference containers, they should be 
implemented either as value-type structs, or classes that can 
work with RefCounted(T). Baking the reference count directly into 
the container is limiting, and buys nothing. I really don't see a 
problem with GC'ed classes if you really want reference types. 
It's going to be forever, if ever before you can actually turn 
off the GC when using Phobos. At least, if it's a class, you can 
use Scoped(T), or RefCounted(T) on it...assuming RefCounted(T) is 
fixed up to work with classes at some point, which seems like a 
better path then baking ref counting into a container 
implementation.


I'm feeling a bit repetitive at this point, and wondering if I 
should have responded to this at all, and I'm sure you know 
exactly what I'm talking about, and that it's a matter of choice 
at this point, but there you have it.


Bit

Re: I hate new DUB config format

[terchestor via Digitalmars-d]

On Monday, 30 November 2015 at 17:53:04 UTC, Ola Fosheim Grøstad 
wrote:

On Monday, 30 November 2015 at 17:18:50 UTC, terchestor wrote:
http://www.easypolls.net/poll.html?p=565587f4e4b0b3955a59fb67 
shows right now that 70% of 98 voters DISILIKE SDL.


Well, most people who didn't object probably didn't bother to 
vote... What about just hashing it out in YAML? It would look 
like this:



# this is a comment

name: my project
description: A little web service of mine.
authors:
- Peter Parker
- Spiderman
homepage: http://myproject.example.com
license: GPL-2.0
dependencies:
vibe-d: ~>0.7.23


10 lines? I rest my case.

Re: I hate new DUB config format

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 18:02:34 UTC, Chris wrote:
YAML takes spaces into account, doesn't it? That's a source of 
unnecessary, Pythonesque bugs.


Most editors support YAML so you should get no Pythonesque bugs 
since they enforce WYSIWYG.  I have more issues with my 
handwritten JSON than YAML.


But there is nothing wrong in constraining the format as long as 
the resulting file is compatible.


http://www.yaml.org/spec/1.2/spec.html#Basic

Re: I hate new DUB config format

[Chris via Digitalmars-d]

On Monday, 30 November 2015 at 18:13:11 UTC, Ola Fosheim Grøstad 
wrote:

On Monday, 30 November 2015 at 18:02:34 UTC, Chris wrote:
YAML takes spaces into account, doesn't it? That's a source of 
unnecessary, Pythonesque bugs.


Most editors support YAML so you should get no Pythonesque bugs 
since they enforce WYSIWYG.  I have more issues with my 
handwritten JSON than YAML.


But there is nothing wrong in constraining the format as long 
as the resulting file is compatible.


http://www.yaml.org/spec/1.2/spec.html#Basic


I once wrote a description in YAML. Spaces (or lack of them) lead 
to stupid errors. Not to mention the pain of copying and pasting 
with different indentation levels. If you have to use an editor 
to help you with indentation levels, there's something wrong, it 
means that it's not trivially easy.


When will people understand that indentation should not be part 
of a language's syntax?

Re: extern(C++, NS)

[Walter Bright via Digitalmars-d]

On 11/30/2015 2:26 AM, Ola Fosheim Grøstad wrote:

I wish someone would shed som light on this as inline namespaces is what
libraries will use in the future in order to do versioning and  target different
architectures, the one marked "inline" is made active and can be directly
accessed through "X::decl" or "X::version1::decl" in c++:

namespace X {
  inline namespace version1 {
   decl
  }
  namespace version2 {
   decl
  }
}

Seems to me that D needs to embed clang and that the current bindings-only
approach will not survive C++11 and later standards.



It'd be worthwhile to learn how D's name lookup system works before declaring it 
lame and insufficient:


  extern (C++, X) {
extern (C++, version1) {
enum e = 3;
}
  }

  int x = e;
  int y = X.e;
  int z = X.version1.e;

compiles successfully.

Re: I hate new DUB config format

[Luis via Digitalmars-d]

On Monday, 30 November 2015 at 17:53:04 UTC, Ola Fosheim Grøstad 
wrote:

On Monday, 30 November 2015 at 17:18:50 UTC, terchestor wrote:
http://www.easypolls.net/poll.html?p=565587f4e4b0b3955a59fb67 
shows right now that 70% of 98 voters DISILIKE SDL.


Well, most people who didn't object probably didn't bother to 
vote... What about just hashing it out in YAML? It would look 
like this:



# this is a comment

name: my project
description: A little web service of mine.
authors:
- Peter Parker
- Spiderman
homepage: http://myproject.example.com
license: GPL-2.0
dependencies:
vibe-d: ~>0.7.23


How do translate this example on SDLang ?

name "dedcpu"
authors "Luis Panadero Guardeño"
targetType "none"
license "BSD 3-clause"
description "DCPU-16 tools"

subPackage {
   name "lem1802"
   description "Visual LEM1802 font editor"
   targetType "executable"
   targetName "lem1802"
   excludedSourceFiles "src/bconv.d"
   excludedSourceFiles "src/ddis.d"
   libs "gtkd" platform="windows"

   configuration "nogtk" {
  platforms "windows"
   }

   configuration "gtk" {
  platforms "posix"
  dependency "gtk-d:gtkd" version="~>3.2.0"
   }
}

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/2015 12:56 PM, bitwise wrote:

On Saturday, 28 November 2015 at 13:39:35 UTC, Andrei Alexandrescu wrote:

On 11/28/15 1:59 AM, bitwise wrote:


Classes/real-ref-types dont act as you're describing, so why should
these fake struct wrapper ref things act this way? This will likely
achieve the exact opposite of what you're aiming for, by making
something that's supposed to act like a reference type have different
behaviour from D's built in ref types.


So what would work for you? -- Andrei


Sorry if that response seemed a tad flippant, but I have to be
honest...I am completely against this design...to put it mildly.

I have my own containers to use, but on top of the fact that I would
prefer something which is collaboratively maintained, I don't want to be
forced to deal with, or support these "reference" containers, which will
most likely happen if they get added to Phobos.

I'm really not sure where to begin tearing this idea apart. The
principal I have a problem with is much more fundamental than this one
decision. In general, there is a lot in D that is very hackish.

I understand that you don't want eager copying of containers, but when I
way predictability, simplicity, clarity, and flexibility against that
concern, there is no way I'm agreeing with you, when you can simply wrap
a proper container in a RefCounted(T) or something. A class is a
reference type, and a struct is a value type. If a user sees a struct,
they should expect a value type which will copy on assign, and if they
see a class, they should expect a reference. In D, the differentiation
between value and reference types is clearly specified, and D users
_should_ be, and should be expected to be, aware of it.

If you really want reference containers, they should be implemented
either as value-type structs, or classes that can work with
RefCounted(T). Baking the reference count directly into the container is
limiting, and buys nothing. I really don't see a problem with GC'ed
classes if you really want reference types. It's going to be forever, if
ever before you can actually turn off the GC when using Phobos. At
least, if it's a class, you can use Scoped(T), or RefCounted(T) on
it...assuming RefCounted(T) is fixed up to work with classes at some
point, which seems like a better path then baking ref counting into a
container implementation.

I'm feeling a bit repetitive at this point, and wondering if I should
have responded to this at all, and I'm sure you know exactly what I'm
talking about, and that it's a matter of choice at this point, but there
you have it.


Thanks, your response is appreciated! Let me make sure I understand. So, 
in your opinion:


* Value containers plus a way to wrap them with RefCounted is a better 
solution than containers with built-in reference semantics.


* The design supported by D most naturally is: classes have reference 
semantics and structs have value semantics.


* Reference semantics for containers seem to work best with GC. Pursuing 
reference containers with baked-in RC seems nonproductive.


This is all sensible. Here are a couple of follow-up questions and 
considerations:


* I couldn't integrate this with the rest of your post: "The principal I 
have a problem with is much more fundamental than this one decision. In 
general, there is a lot in D that is very hackish." Could you please 
elaborate?


* The one matter with the value/RefCounted approach is that RefCounted 
cannot be made @safe. One core design decision I made was to aim for 
safe containers. I do agree that if safety is off the table, your design 
would be a very good choice (probably the best I can think of, and I'd 
start an implementation using it).



Thanks,

Andrei

Re: I hate new DUB config format

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 18:07:20 UTC, Luis wrote:

How do translate this example on SDLang ?


You can translate it by following these patterns:

http://www.yaml.org/spec/1.2/spec.html#Preview

As you see, you have some room for making it more dense if you 
want to. So you can tailor it a bit to your own taste.

Re: I hate new DUB config format

[Chris via Digitalmars-d]

On Monday, 30 November 2015 at 17:53:04 UTC, Ola Fosheim Grøstad 
wrote:

On Monday, 30 November 2015 at 17:18:50 UTC, terchestor wrote:
http://www.easypolls.net/poll.html?p=565587f4e4b0b3955a59fb67 
shows right now that 70% of 98 voters DISILIKE SDL.


Well, most people who didn't object probably didn't bother to 
vote... What about just hashing it out in YAML? It would look 
like this:



# this is a comment

name: my project
description: A little web service of mine.
authors:
- Peter Parker
- Spiderman
homepage: http://myproject.example.com
license: GPL-2.0
dependencies:
vibe-d: ~>0.7.23


YAML takes spaces into account, doesn't it? That's a source of 
unnecessary, Pythonesque bugs.

Re: I hate new DUB config format

[Atila Neves via Digitalmars-d]

On Sunday, 29 November 2015 at 22:52:20 UTC, Ola Fosheim Gr wrote:
On Sunday, 29 November 2015 at 18:54:04 UTC, Russel Winder 
wrote:
hand lots of people seem addicted to JSON. On the fourth hand 
I cannot get worked up about this, it is just a build 
specification script which really ought to be written in D. cf.


What is the advantage of having it in an imperative language, 
though? Isn't a concurrent deductive language better and faster?


As much as possible, yes. But non-trivial builds require a DAG, 
ordering, and plain just telling the computer what to do.


I've written quite a bit of CMake script to handle complicated 
builds. When you need it, you want a full language. I've heard 
horror stories of people doing boolean logic and loops in XML for 
Ant. CMake script is bad enough, I can't imagine how much I'd 
bang my head against the wall trying to contort XML into a bad 
version of Lisp.


The truth is, for most projects a `dub build` will do, and that's 
fine. Declarative is the way to go then. But when you have 
binaries reading files to auto-generate code that then gets 
compiled in two different ways, one of which is copied... you get 
the idea.


Atila

An interesting data structure with search time O(sqrt n)

[Andrei Alexandrescu via Digitalmars-d]

Okasaki's book is a continued inspiration of data structures and algorithms.

I was thinking along the following lines: typical collections are 
searchable in linear time. Then we have highly structured collections 
that feature logarithmic search time. But there seems to be nothing in 
between. So I was thinking, what would be a data structure that allows 
O(sqrt n) search times?


After a little tinkering, here's what I came up with.

Start with a simple array of data. Then mentally decompose that array 
into a concatenation of smaller arrays: first has size 1, second has 
size 4, third has size 9, then 16, 25, 36, ... Generally the size of 
these imaginary subarrays grows quadratically. And they're adjacent to 
each other. The last array may be incomplete.


Example: we decompose an array of size 35 into: an array of size 1 
followed by arrays of sizes 4, 9, 16, 5 (last being an incomplete 
fragment of an array of size 25).


Now each of these arrays we organize as a max heap. Moreover, we arrange 
data such that the maximums of these heaps are in INCREASING order. That 
means the smallest element of the entire (initial) array is at the first 
position, then followed by the next 4 smallest organized in a max heap, 
followed by the next 9 smallest organized in a max heap, ... etc. There 
are a total of O(sqrt n) heaps, and each has O(sqrt n) elements.


That's the layout! Now, to search we look at one heap at a time. 
Whenever the maximum element (first element in the subarray) is smaller 
than the searched value, we skip over that entire heap and go to the 
next one. In the worst case we'll skip O(sqrt n) heaps. When the max 
value in a heap is less than the searched element, we found the heap and 
we run a linear search among O(sqrt n) elements.


The structure is nice for sorting and in particular parallel sorting 
because each subarray can be sorted independently - there's no migration 
into or out of each subarray. Inside each subarray, of course heapsort 
would be a good choice because it takes advantage of the existing max 
heap. 	


I haven't worked out the math for insertion and deletion yet, but they 
seem to also be around O(sqrt n) or O(log(n) * sqrt(n)). Just wanted to 
share with you and discuss what seems to be an interesting data structure.


Please share any thoughts!


Andrei

Re: I hate new DUB config format

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 18:50:57 UTC, Russel Winder wrote:
you had to write you own Java coded Maven plugin. So having a 
language which can offer a declarative DSL and the ability to 
do a bit of imperative stuff if it is needed, you get a good 
system. SCons and Gradle both do this: mostly declarative with 
bits as needed.


I don't know them, I am sure you have a point :).  But 
intuitively I think that modern build systems _ought_ to use a 
constraints-based language and be geared towards distributed 
builds... take that as an heartfelt opinion, not a fact.




However in doing this there is often forward progress in build.


GNU make is good enough for my own stuff, but probably not so 
good for cross platform builds.


As for package managers, I'd much rather have a really good 
generic repository (like Debian) with precompiled vetted and 
patched quality libraries than all these language specific ones 
where 99% is useless/unfinished/unmaintained.


Take a look at node.js: 210820 packages. How do you find new gems 
in that mess? It is also becoming increasingly difficult to find 
quality stuff on github by searching IMO. Too much dead 
unfinished stuff. Maybe that's why Open Source repository sites 
die. They drown in dead code.


Besides, dealing with 10 different packaging systems, potential 
security risks and potential configuration conflicts is not 
entertaining.


In the end though Lisp is the one true language, so we should 
all just write in Lisp.


Yes, keep it simple and do numbers in unary notation.

Re: I hate new DUB config format

[Atila Neves via Digitalmars-d]

On Sunday, 29 November 2015 at 18:54:04 UTC, Russel Winder wrote:
On Sun, 2015-11-29 at 17:25 +, Poyeyo via Digitalmars-d 
wrote:



[…]

C/C++ make/cmake/nmake -> here be dragons


Or SCons if you want to be cool. I guess Bazel (and maybe Tup) 
might

become trendy.


perl CPANfile -> something perly
java maven -> xml


Does anyone still use Maven – surely the world has moved to 
Gradle with it's Groovy scripts using the Gradle DSL.



ruby gemfile -> ruby
python pip -> python egg


Python has moved to wheels, eggs were always crap.


php composer -> json
node.js npm -> json
go godep -> json


I am not sure this as as mainstream as this comment implies. 
Also a lot of people are using gb.



rust cargo -> rust manifest


Which is TOML.


d dub -> json and sdlang


Personally I abhor JSON for this kind of specification, it a 
transfer notation between computers, cf. XML. On the other hand 
I couldn't get SDL specs working. I will undoubtedly try again 
as SDL is just so much nicer than JSON for this. On the third 
hand lots of people seem addicted to JSON. On the fourth hand I 
cannot get worked up about this, it is just a build 
specification script which really ought to be written in D. cf. 
SBT for Scala uses Scala. Leiningen for Clojure uses Clojure. 
These languages have the right idea.


Oh, I just got worked up about this.


You can write build descriptions in D today:

http://code.dlang.org/packages/reggae

Package dependencies still comes from dub, so JSON or SDL are 
needed for that. Any project that needs an imperative language to 
describe its build can use reggae for the heavy lifting and dub 
to specify dependencies. You don't even have to use dub if you 
don't want to.


Atila

Re: extern(C++, NS)

[Walter Bright via Digitalmars-d]

On 11/30/2015 10:51 AM, Ola Fosheim Grøstad wrote:

On Monday, 30 November 2015 at 17:38:06 UTC, Walter Bright wrote:

It'd be worthwhile to learn how D's name lookup system works before declaring
it lame and insufficient:


Nobody has said anything about lame. The issue is that you don't need to know of
"version1" on the C++ side.


Did you look at the example I posted?


One purpose is to use the "inline" as a switch, so
that you can use macros to turn on and off different library subsets. "inline"
is injected in front of namespaces that are to be accessible in the parent, and
that injection can be done by a macro.

But on the D side you need to know of "version1" if D does not parse C++
headers. Which is a maintenance burden.


Please examine the example I gave again before assuming how D works.

Re: Can't understand how to do server response with vibed

[Sebastiaan Koppe via Digitalmars-d-learn]

On Sunday, 29 November 2015 at 07:37:56 UTC, Suliman wrote:
On Saturday, 28 November 2015 at 23:21:21 UTC, Sebastiaan Koppe 
wrote:

On Saturday, 28 November 2015 at 19:05:59 UTC, Suliman wrote:
And also I can't understand difference between 
HTTPClientRequest and HTTPServerRequest


If the application (vibe.d) makes a request, it is the client. 
If the request is made to your application, it is the server.


In your case your angular app is the client, and your vibe.d 
app is the server. Therefor, HTTPServer(Request|Response).


Could you explain me about: HTTPServerRequest and HTTPRequest. 
I can't understand difference.


No idea. Probably HTTPRequest provides common functionality for 
both HTTPServerRequest and HTTPClientRequest. Just guessing.

Re: vibe.d-example illustrating Dynamic Textual Web-Interface

[Sebastiaan Koppe via Digitalmars-d-learn]

On Monday, 30 November 2015 at 10:08:17 UTC, Nordlöw wrote:

Can somebody please show a enlightening example of, so called,

"revamp of the REST interface generator"

added to release 0.7.26 at:

http://vibed.org/blog/posts/vibe-release-0.7.26

I want to use vibe.d to add a modern dynamic web-interface to 
my knowledge graph I'm currently developing.


More specifically I would like an interface that makes rich use 
of dynamic HTML. When the user changes the contents of a 
search/command-line text-field the client logic shall on the 
fly (after a certain delay) lookup related information with 
vibe.d-server and present the user with relevant hits or 
completions in a another part of page (HTML div-block).


Does anybody have a similar vibe.d-project to be inspired from, 
in this regard?


I have written a mpd (Music Player Daemon) client in D and just 
finished the web app (bar a couple of features).


All of the rendering is done on the client and only json data is 
transmitted between server and web app. Just finished the 
WebSocket part so if anybody changes the music/volume/playlist, 
all clients update the interface.


The code could use a cleanup/refactoring but everything is 
working.


The D parts of interest are the MpdApiInterface1 and MpdApi1 
classes in source/app.d


For the JS parts you can start with source/index.js, but its full 
of ES6 classes and react code. So that might not be your cup of 
tea. In index.js there are mainly React Classes (basically html 
renderers) and React Container Classes (basically code handling 
input changes).


In the source/actions folder there are some js files that call 
the server and modify state (volume/song). In the source/stores 
folder, some js files that only retrieve data.


The js architecture if influenced by react/flux/facebook's, but I 
am toying with it to see what fits for me. Specifically I rely a 
lot on RxJS for the observables.


For the project I decided to put js and d files in the same 
folders. That might not have been a good idea. Also dub has some 
issues with one of the D dependencies that I haven't updated in 
months.


Code can be found here: https://bitbucket.org/skoppe/mpc/src

Re: This Week in D

[Adam D. Ruppe via Digitalmars-d]

I'll change it to "thread" on the front page.

[Issue 15378] dlang.org does not completely work with https:

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15378

--- Comment #3 from David Nadlinger  ---
(In reply to Adam D. Ruppe from comment #2)
> The whole url bar showing as green is kinda rare, that signifies the
> extended validation thing. My bank does it but no other site I go to does.

I'm not talking about extended validation; just about Chrome even showing a
lock symbol (which happens to be green, and also causes the https schema part
of the URL to be rendered green).

For example, https://www.rust-lang.org/ and https://golang.org/ show up as
"secure" in this way on Chrome/OS X, while https://dlang.org does not.

--

Re: An interesting data structure with search time O(sqrt n)

[H. S. Teoh via Digitalmars-d]

On Mon, Nov 30, 2015 at 03:13:11PM -0500, Andrei Alexandrescu via Digitalmars-d 
wrote:
> Okasaki's book is a continued inspiration of data structures and
> algorithms.
> 
> I was thinking along the following lines: typical collections are
> searchable in linear time. Then we have highly structured collections
> that feature logarithmic search time. But there seems to be nothing in
> between. So I was thinking, what would be a data structure that allows
> O(sqrt n) search times?
> 
> After a little tinkering, here's what I came up with.

Interesting indeed.

It leaves me wondering, though, what's the point of having an O(sqrt n)
collection? What are the advantages?  Why would I use this structure
instead of, say, a traditional array heap with O(log n) search time?


T

-- 
Why are you blatanly misspelling "blatant"? -- Branden Robinson

Re: vibe.d-example illustrating Dynamic Textual Web-Interface

[David DeWitt via Digitalmars-d-learn]

On Monday, 30 November 2015 at 20:05:42 UTC, Sebastiaan Koppe 
wrote:



Code can be found here: https://bitbucket.org/skoppe/mpc/src


Looks good.  Have you looked at Redux and Webpack?  I am working 
on a Redux example and we have switched to Webpack and Redux at 
work and it is nice.

Re: DUB, Platform specifications and dependencies

[Zardoz via Digitalmars-d-learn]

On Monday, 30 November 2015 at 16:54:43 UTC, Sönke Ludwig wrote:

Am 24.11.2015 um 19:51 schrieb Zardoz:
Actually I'm trying to setup dub to not grab a dependency on 
Windows (

https://github.com/Zardoz89/DEDCPU-16/blob/master/dub.sdl ) :

name "dedcpu"
authors "Luis Panadero Guardeño"
targetType "none"
license "BSD 3-clause"
description "DCPU-16 tools"

subPackage {
   name "lem1802"
   description "Visual LEM1802 font editor"
   targetType "executable"
   targetName "lem1802"
   excludedSourceFiles "src/bconv.d"
   excludedSourceFiles "src/ddis.d"
   dependency "gtk-d:gtkd" version="~>3.2.0" platform="posix"
   libs "gtkd" platform="windows"
}

...

How ever, running dub on Windows (tested on two different 
machines),
ignores platform specification for gtk-d dependency . What I'm 
doing

wrong ?


Platform specifications are currently not supported for 
dependencies due to the way the dependency resolver works. 
However, it is possible to use platform specific configurations 
for this purpose:


name "dedcpu"
authors "Luis Panadero Guardeño"
targetType "none"
license "BSD 3-clause"
description "DCPU-16 tools"

subPackage {
   name "lem1802"
   description "Visual LEM1802 font editor"
   targetType "executable"
   targetName "lem1802"
   excludedSourceFiles "src/bconv.d"
   excludedSourceFiles "src/ddis.d"
   libs "gtkd" platform="windows"

   configuration "nogtk" {
  platforms "windows"
   }

   configuration "gtk" {
  platforms "posix"
  dependency "gtk-d:gtkd" version="~>3.2.0"
   }
}


Thanks!! I ended doing some minor change to get it working :

subPackage {
  name "lem1802"
  description "Visual LEM1802 font editor"
  excludedSourceFiles "src/bconv.d"
  excludedSourceFiles "src/ddis.d"

  configuration "nogtk" {
targetType "executable"
targetName "lem1802"
platform "windows"
libs "gtkd"
  }

  configuration "gtk" {
targetType "executable"
targetName "lem1802"
platform "posix"
dependency "gtk-d:gtkd" version="~>3.2.0"
  }
}

Re: An interesting data structure with search time O(sqrt n)

[Dmitry Olshansky via Digitalmars-d]

On 30-Nov-2015 23:13, Andrei Alexandrescu wrote:

Okasaki's book is a continued inspiration of data structures and
algorithms.

I was thinking along the following lines: typical collections are
searchable in linear time. Then we have highly structured collections
that feature logarithmic search time. But there seems to be nothing in
between. So I was thinking, what would be a data structure that allows
O(sqrt n) search times?

After a little tinkering, here's what I came up with.

Start with a simple array of data. Then mentally decompose that array
into a concatenation of smaller arrays: first has size 1, second has
size 4, third has size 9, then 16, 25, 36, ... Generally the size of
these imaginary subarrays grows quadratically. And they're adjacent to
each other. The last array may be incomplete.

Example: we decompose an array of size 35 into: an array of size 1
followed by arrays of sizes 4, 9, 16, 5 (last being an incomplete
fragment of an array of size 25).

Now each of these arrays we organize as a max heap. Moreover, we arrange
data such that the maximums of these heaps are in INCREASING order. That
means the smallest element of the entire (initial) array is at the first
position, then followed by the next 4 smallest organized in a max heap,
followed by the next 9 smallest organized in a max heap, ... etc. There
are a total of O(sqrt n) heaps, and each has O(sqrt n) elements.

That's the layout! Now, to search we look at one heap at a time.
Whenever the maximum element (first element in the subarray) is smaller
than the searched value, we skip over that entire heap and go to the
next one. In the worst case we'll skip O(sqrt n) heaps. When the max
value in a heap is less than the searched element, we found the heap and
we run a linear search among O(sqrt n) elements.


Reminds me of Van Emde Boas layout which is however fractal in nature: 
sqrt(N) pieces each having sqrt(N) element are subdivided again into 
sqrt(sqrt(N)) pieces and so on.


Not sure if you have seen, but see also cache-oblivious data-structures:
http://erikdemaine.org/papers/BRICS2002/paper.pdf


--
Dmitry Olshansky

Re: I hate new DUB config format

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 19:36:18 UTC, Atila Neves wrote:
As much as possible, yes. But non-trivial builds require a DAG, 
ordering, and plain just telling the computer what to do.


Representing a DAG in a logic language is not a problem. The 
biggest problem is probably that most programmers (myself 
included) have an imperative mindset.


for Ant. CMake script is bad enough, I can't imagine how much 
I'd bang my head against the wall trying to contort XML into a 
bad version of Lisp.


I don't know much about CMake, only given it a glance as 
make+Python is good enough for me. But I see your point. I don't 
know how expressive CMake is, but it does take quite a bit of 
adjustment to express oneself in a deductive (logic) language.


The truth is, for most projects a `dub build` will do, and 
that's fine. Declarative is the way to go then. But when you 
have binaries reading files to auto-generate code that then 
gets compiled in two different ways, one of which is copied... 
you get the idea.


Hmm, yes, but if we (in fantasy land) start from scratch and have 
a generic distributed build system with a shared nosql database 
for the intermediate results and some kind of linda-like tuple 
space to back it up with meta data. Then a deductive language to 
update the tuple space. Then you have regular executable workers 
pull stuff out of the linda-space, and put the results back in. 
Unlike a file system, it would be transactional.

Problems loading libcurl.so and running datetime unittest on NixOS package build

[Thomas Mader via Digitalmars-d]

I created a bug but wanted to get some opinions regarding the 
solution.
You can read about the problem in 
https://issues.dlang.org/show_bug.cgi?id=15391#c3 .



Thomas

Re: vibe.d-example illustrating Dynamic Textual Web-Interface

[Sebastiaan Koppe via Digitalmars-d-learn]

On Monday, 30 November 2015 at 20:23:48 UTC, David DeWitt wrote:
Have you looked at Redux and Webpack?  I am working on a Redux 
example and we have switched to Webpack and Redux at work and 
it is nice.


I know about both yes. Webpack would probably beat browserify, 
but I haven't gotten the time to migrate myself. Their hot code 
reloading looks good though.


Isn't redux the client side for GraphQL? I followed it a bit but 
it being so fresh, decided to wait.


A GraphQL interface generator for vibe.d would be nice.

Re: vibe.d-example illustrating Dynamic Textual Web-Interface

[David DeWitt via Digitalmars-d-learn]

On Monday, 30 November 2015 at 20:38:12 UTC, Sebastiaan Koppe 
wrote:

On Monday, 30 November 2015 at 20:23:48 UTC, David DeWitt wrote:
Have you looked at Redux and Webpack?  I am working on a Redux 
example and we have switched to Webpack and Redux at work and 
it is nice.


I know about both yes. Webpack would probably beat browserify, 
but I haven't gotten the time to migrate myself. Their hot code 
reloading looks good though.


Isn't redux the client side for GraphQL? I followed it a bit 
but it being so fresh, decided to wait.


A GraphQL interface generator for vibe.d would be nice.


Redux is luscious!!!  It is a flux-like implementation but you 
dont have to deal with individual stores as the app's state lives 
in a single object tree. Once you go thru it you'll like it.



https://github.com/rackt/redux

https://github.com/xgrommx/awesome-redux

Re: JSON5 support for std.json

[Jack Stouffer via Digitalmars-d]

On Monday, 30 November 2015 at 16:12:07 UTC, Chris Wright wrote:
The reason to incorporate it into the standard library 
interpretation is because it's mostly identical to JSON, so 
sharing implementations is obvious.


That doesn't follow. Just because implementations are mostly 
shared doesn't mean that it should be included into Phobos. 
Someone still needs to maintain your new code and the cost 
benefit analysis still needs to happen.


For instance, a feature request for Newtonsoft JSON.NET (which 
is the most
well known JSON library for .NET) to support JSON5 pretty much 
went "What's JSON5?" and then "Oh, we already support 90% of 
that".


So the authors of one of the most well known JSON libraries has 
also never heard of it.


The recent thread about DUB's config format would have been 
much more strongly

in favor of JSON if std.json supported JSON5.


How much stronger can you get than almost everyone but like three 
people being in favor of JSON over SDL?


Again, I see no evidence that JSON5 is at all popular. I can list 
well over 2000 popular repos on Github that use JSON in some way, 
either with APIs or config files, etc. So show me at least 50 
github repos with over 500 stars that use JSON5 (meaning they are 
not JSON5 parsers) and I will change my mind. 50 is not an 
unreasonable number to ask for, as you want this to go into 
Phobos, this needs a lot of ground swell and use.


JSON5 is also just a terrible idea. There is a very good reason 
why JSON does not have comments 
https://plus.google.com/+DouglasCrockfordEsq/posts/RK8qyGVaGSr 
and why it's strict. Data formats should have data, not anything 
else. It's bare bones structure and strictness makes standard 
following parsers extremely fast, in fact the fastest serializers 
ever. Loose data formats are a nightmare to work with, XML being 
the front runner in this regard, as parsing is slow and data can 
be stored and accessed in tons of different ways.


As I mentioned earlier, JSON5 is not JSON, it's something else. 
There is only one JSON and calling what ever this is JSON is 
disingenuous on the part of the creator. So even if this got into 
Phobos, it shouldn't go into std.json.


If you want a human readable format, just use YAML and use one of 
the many, many cross compilers of YAML to JSON.

Re: I hate new DUB config format

[Suliman via Digitalmars-d]

Should we try to implement yet another language for writing 
building config? Maybe we should use any of existence language 
that may be very good for it, like Red. It have very small foot 
prints so it can be easy to embeded to build system.

Re: extern(C++, NS)

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 19:38:53 UTC, Walter Bright wrote:

On 11/30/2015 10:51 AM, Ola Fosheim Grøstad wrote:
On Monday, 30 November 2015 at 17:38:06 UTC, Walter Bright 
wrote:
It'd be worthwhile to learn how D's name lookup system works 
before declaring

it lame and insufficient:


Nobody has said anything about lame. The issue is that you 
don't need to know of

"version1" on the C++ side.


Did you look at the example I posted?


Yes, the problem I see is:

1. You need to know about "version1" which is an internal 
namespace on the C++ side, so you cannot just create binding to 
the documented API, but need to go through the source code just 
to discover that "version1" exists.


2. If the library internals changes on the C++ side it causes 
problems for D application code, but not for C++ application code.


3.  In order to keep the D and the C++ side call the same set of 
APIs (if desired) you also need to know on the D side whether the 
current C++ configuration has enabled "version1" or "version2" (+ 
a bunch of other potential variations).


In essence the C++ model isn't friendly to foreign languages. 
They keep bolting on "neat hacks" to extend the language in 
nonbreaking "transparent" ways (on the C++ side).

Re: Is there anyone willing to do the videos 18sex website?

[mcss via Digitalmars-d-announce]

Thanks to a friend's attention, but in our country is not allowed 
to do this type of website, belonging to the crime, I now have a 
headache this thing! Do you have any good ideas?

[Issue 15172] ICE(interpret.c ctfeCompile) Assertion `!fd->semantic3Errors' failed.

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15172

--- Comment #2 from github-bugzi...@puremagic.com ---
Commits pushed to master at https://github.com/D-Programming-Language/dmd

https://github.com/D-Programming-Language/dmd/commit/0ff99ff004c49a370f2a014dbcd1cec0cf053f63
fix Issue 15172 - ICE(interpret.c ctfeCompile) Assertion `!fd->semantic3Errors'
failed.

https://github.com/D-Programming-Language/dmd/commit/d2880137c7a25e6cd167a713cdcec71b7910cb6f
Merge pull request #5168 from 9rnsr/fix15172

Issue 15172 - ICE(interpret.c ctfeCompile) Assertion `!fd->semantic3Errors'
failed.

--

[Issue 15172] ICE(interpret.c ctfeCompile) Assertion `!fd->semantic3Errors' failed.

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15172

github-bugzi...@puremagic.com changed:

   What|Removed |Added

 Status|NEW |RESOLVED
 Resolution|--- |FIXED

--

Re: An interesting data structure with search time O(sqrt n)

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 3:29 PM, Dmitry Olshansky wrote:

Reminds me of Van Emde Boas layout which is however fractal in nature:
sqrt(N) pieces each having sqrt(N) element are subdivided again into
sqrt(sqrt(N)) pieces and so on.

Not sure if you have seen, but see also cache-oblivious data-structures:
http://erikdemaine.org/papers/BRICS2002/paper.pdf


Thanks, I'll look these up! -- Andrei

Re: An interesting data structure with search time O(sqrt n)

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 3:20 PM, H. S. Teoh via Digitalmars-d wrote:

On Mon, Nov 30, 2015 at 03:13:11PM -0500, Andrei Alexandrescu via Digitalmars-d 
wrote:

Okasaki's book is a continued inspiration of data structures and
algorithms.

I was thinking along the following lines: typical collections are
searchable in linear time. Then we have highly structured collections
that feature logarithmic search time. But there seems to be nothing in
between. So I was thinking, what would be a data structure that allows
O(sqrt n) search times?

After a little tinkering, here's what I came up with.


Interesting indeed.

It leaves me wondering, though, what's the point of having an O(sqrt n)
collection? What are the advantages?  Why would I use this structure
instead of, say, a traditional array heap with O(log n) search time?


(Heaps offer only linear search time. You may take advantage of the heap 
structure to skip portions of the array, but on average and in the worst 
case the search is still O(n). So I assume you meant "sorted array or 
one of the classic search trees".)


The motivation starts with a desire to use arrays as the fundamental 
layout. There have been many trends in computing as of late, among 
which: cache hierarchies are here to stay and contiguous layout is 
preferable.


The short of it is, arrays are king. No two ways about it - following 
pointers is a losing strategy when there's an alternative. A variety of 
new data structures (Clojure's arrays, heaps with tombstones) avoid 
classic pointer-based data structures in favor of adding structure on 
top of arrays.


So now if we consider thinking, "how do we organize an array for good 
search performance" we have a spectrum. Generally we also care about 
insertion and removal.


At one end of the spectrum there's doing nothing at all - that means 
O(1) build (nothing to do), O(n) search, O(1) insert (just append it), 
O(n) removal. Not very nice.


At the other end, the absolute best structuring on top of an array for 
search is sorting. With sorting you get great O(log n) search 
performance. But the others are not nice - O(n log n) build, O(n) add, 
O(n) remove.


So now consider my square heaps. We have O(n) build time (just a bunch 
of heapifications) and O(sqrt n) search. Then (again I haven't worked 
out the math yet) let's assume insertion and removal are both O(sqrt n). 
Then you get something less structured than full sorting, but also just 
good enough to offer the same complexity for each of search, insert, and 
delete. That would be pretty neat.



Andrei

Re: An interesting data structure with search time O(sqrt n)

[Sriram Srinivasan via Digitalmars-d]

The key search phrase is "cache oblivious data structures". One 
of the cache-friendly layouts is the van Emde Boas tree.