Re: Challenge Tuples
On Friday, 3 May 2024 at 05:11:28 UTC, Salih Dincer wrote:
..
Wouldn't it be great if there was a feature that worked at
runtime...
SDB@79
module m;
@safe:
private:
import std;
void main()
{
auto myTuple = tuple(1, 2, 3, [1, 3], 5);
int[] arrToSum;
foreach(int i, val; myTuple.expand)
{
if(typeof(val).stringof == "int[]")
{
foreach(v; myTuple.expand[i..i+1])
arrToSum ~= v;
}
else
{
arrToSum ~= val;
}
}
writefln("The total value of the tuples is: %s",
arrToSum.sum); // 15
}
Re: Challenge Tuples
On Wednesday, 1 May 2024 at 14:15:19 UTC, Andrey Zherikov wrote:
Shorter and without allocations:
```d
import std.typecons : tuple;
import std.algorithm : sum, each;
auto sum(int i) => i;
void main()
{
auto t = tuple(1, 2, 3, [1, 3], 5);
int res=0;
t.each!(e => res += sum(e));
assert(res == 15);
}
```
Super!
In summary, D is clearly ahead of the tuple. Especially with its
features similar to AliasSeq, I think it is unrivaled. Wouldn't
it be great if there was a feature that worked at runtime...
SDB@79
Re: Challenge Tuples
On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and
implement the sum (total = 15) with the least codes using the
sum() function of the language you are coding...
Let's start with D:
```d
import std.typecons : tuple;
import std.algorithm : sum;
void main()
{
auto t = tuple(1, 2, 3, [1, 3], 5);
int[] arr;
t.each!(e => arr ~= e);
assert(arr.sum == 15);
}
```
and bonus:
```d
import std.typecons : tuple;
import std.stdio : writeln;
void main()
{
auto t = tuple(1, 2, 3, [1, 3], 5);
auto results = [0];
foreach (data; t)
{
static
if (is(typeof(data) == int[]))
{
int sum;
foreach (d; data)
{
sum += d;
}
results ~= sum;
}
else
{
results ~= data;
}
}
results.writeln; // [0, 1, 2, 3, 4, 5]
```
I bet you won't be able to do it this easily with other
languages! Note: I tried with C# and Python and it didn't work!
SDB@79
Shorter and without allocations:
```d
import std.typecons : tuple;
import std.algorithm : sum, each;
auto sum(int i) => i;
void main()
{
auto t = tuple(1, 2, 3, [1, 3], 5);
int res=0;
t.each!(e => res += sum(e));
assert(res == 15);
}
```
Re: Challenge Tuples
On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote: You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and implement the sum (total = 15) with the least codes using the sum() function of the language you are coding... Nim: ```nim import std/[math, typetraits, macros] macro unrollRange(low, high: static int; name, body: untyped) = result = newStmtList() for i in low ..< high: result.add(newBlockStmt(newStmtList( newConstStmt(name, newLit i), copy body ))) let t = (1, 2, 3, @[1, 3], 5) var arr: seq[int] unrollRange(0, t.tupleLen, i): arr.add t[i] doAssert arr.sum == 15 ``` vs. D 1. there's no `each` on tuples 2. there's no static for loop, so a macro is needed for the tuple indices 3. `add` is making use of the same overload as D's `~=`
Re: Challenge Tuples
On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and
implement the sum (total = 15) with the least codes using the
sum() function of the language you are coding...
Let's start with D:
```d
import std.typecons : tuple;
import std.algorithm : sum;
void main()
{
auto t = tuple(1, 2, 3, [1, 3], 5);
int[] arr;
t.each!(e => arr ~= e);
assert(arr.sum == 15);
}
```
I bet you won't be able to do it this easily with other
languages! Note: I tried with C# and Python and it didn't work!
For Python it is possible to use something like:
```python
t = (1,2,3,[1,3],5)
for e in t:
a.append(e) if isinstance(e, int) else a.extend(e)
print(sum(a))
```
Re: Challenge Tuples
On Saturday, 27 April 2024 at 15:36:40 UTC, Nick Treleaven wrote:
On Saturday, 27 April 2024 at 15:32:40 UTC, Nick Treleaven
wrote:
On Saturday, 27 April 2024 at 11:55:58 UTC, Basile B. wrote:
foreach const e in u do
if echo(is, e, T) do
result += e;
static if (is(typeof(e) == int))
r += e;
Actually I would write that:
```d
R r;
foreach (e; v)
{
static if (is(typeof(e) : R))
```
I like the new sum() function, great Nick! Moreover, it also
works with an ordinary range:
```d
enum limit = 100; // sum = 5050
iota(limit + 1).sum.writeln;
```
Python seems too complicated to me, but C# looks delicious.
Moreover, it was implemented without defining IEnumerator. Well
done Matheus!
SDB@79
Re: Challenge Tuples
On Saturday, 27 April 2024 at 15:32:40 UTC, Nick Treleaven wrote:
On Saturday, 27 April 2024 at 11:55:58 UTC, Basile B. wrote:
foreach const e in u do
if echo(is, e, T) do
result += e;
static if (is(typeof(e) == int))
r += e;
Actually I would write that:
```d
R r;
foreach (e; v)
{
static if (is(typeof(e) : R))
```
Re: Challenge Tuples
On Saturday, 27 April 2024 at 11:55:58 UTC, Basile B. wrote:
Here's [STYX](https://gitlab.com/styx-lang/styx) solution:
function sum[T,U](U u): u32
I think you meant `: T`.
{
var T result;
foreach const e in u do
if echo(is, e, T) do
result += e;
else do
result += sum;
return result;
}
function main(): s32
{
assert((1, 2, 3, [1, 3], 5).sum![u32]() == 15);
return 0;
}
Mostly equivalent D:
```d
R sum(R = long, T)(T v)
{
R r;
foreach (e; v)
{
static if (is(typeof(e) == int))
r += e;
else
r += sum!R(e);
}
return r;
}
void main()
{
import std;
assert(tuple(1, 2, 3, [1, 3], 5).sum == 15);
}
```
Re: Challenge Tuples
On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and
implement the sum (total = 15) with the least codes using the
sum() function of the language you are coding...
Let's start with D:
Here's [STYX](https://gitlab.com/styx-lang/styx) solution:
function sum[T,U](U u): u32
{
var T result;
foreach const e in u do
if echo(is, e, T) do
result += e;
else do
result += sum;
return result;
}
function main(): s32
{
assert((1, 2, 3, [1, 3], 5).sum![u32]() == 15);
return 0;
}
A few notes:
- tuples are first class citizen
- `foreach` over tuple is like in D, i.e unrolling
- `echo` is like D `__traits`
- _Implicit Generic Application_ of `U` (that's like D's IFTI)
makes the task easy
Re: Challenge Tuples
On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote: You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and implement the sum (total = 15) with the least codes using the sum() function of the language you are coding... My Python solution (function named dosum to avoid collision w. Python primitive): def dosum(itm): if isinstance(itm, (int, float)): return itm return sum( dosum(_i) for _i in itm ); print dosum( [1, 2, 3, [1, 3], 5] )
Re: Challenge Tuples
On Friday, 26 April 2024 at 13:25:34 UTC, Salih Dincer wrote:
...
Very nice, for your first example I need to think a bit because
I'm bit rusty in C#, but I think it will not be as easier as D
version.
For the bonus part:
private static void Main(string[] args){
var a = (1,2,3,(1,3),5);
var t = a as ITuple;
var xx = new List();
for(var i=0;i if(t[i].GetType() ==
typeof(System.ValueTuple)){
var t2 = (t[i] as ITuple);
var s = 0;
for(var j=0;jAgain I'm rusty in C#... but so far yes it's more verbose than
the D version.
Matheus.
Challenge Tuples
You have a 5-item data tuples as Tuple(1, 2, 3, [1, 3], 5) and
implement the sum (total = 15) with the least codes using the
sum() function of the language you are coding...
Let's start with D:
```d
import std.typecons : tuple;
import std.algorithm : sum;
void main()
{
auto t = tuple(1, 2, 3, [1, 3], 5);
int[] arr;
t.each!(e => arr ~= e);
assert(arr.sum == 15);
}
```
and bonus:
```d
import std.typecons : tuple;
import std.stdio : writeln;
void main()
{
auto t = tuple(1, 2, 3, [1, 3], 5);
auto results = [0];
foreach (data; t)
{
static
if (is(typeof(data) == int[]))
{
int sum;
foreach (d; data)
{
sum += d;
}
results ~= sum;
}
else
{
results ~= data;
}
}
results.writeln; // [0, 1, 2, 3, 4, 5]
```
I bet you won't be able to do it this easily with other
languages! Note: I tried with C# and Python and it didn't work!
SDB@79
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
Bit fields are currently going through the DIP process, although because of ImportC having it, its just a matter of turning them on and adding the parser stuff. However there is a major drawback to it and is why you'll still need to use a struct and that is you can't take a pointer to it.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Sat, Mar 16, 2024 at 09:16:51PM +, Liam McGillivray via Digitalmars-d-learn wrote: > On Friday, 15 March 2024 at 00:21:42 UTC, H. S. Teoh wrote: [...] > > When dealing with units of data smaller than a byte, you generally > > need to do it manually, because memory is not addressable by > > individual bits, making it difficult to implement things like > > slicing an array of bool. [...] > I'm curious as to what "manual implementation" would mean, since > clearly making my own struct with `bool[3]` doesn't count. Does D have > features for precise memory manipulation? Manual implementation as in you would deal with the machine representation in terms of bytes, or more likely, uints (on modern CPUs even though bytes are individually addressible, the hardware actually works in terms of a larger unit, typically an 4-byte 32-bit unit, or an 8-byte 64-bit unit), using bitwise operators to manipulate the bits the way you want to. > Anyway, I'm surprised that D has a special operator `&=` for doing bit > manipulation on integers, especially given that the steps to convert > an int into a bool array is more complicated. I would imagine the > former would be a rather niche thing. You should understand that bitwise operators are directly implemented in hardware, and thus operators like &, |, ^, <<, >>, ~, etc., typically map directly to individual CPU instructions. As such, they are very fast, and preferred when you're doing bit-level manipulations. At this level, you typically do not work with individual bits per se, but with machine words (typically 32-bit or 64-bit units). Bitwise operators operate on all 32 or 64 bits at once, so performance-aware code typically manipulates all these bits simultaneously rather than individually. Of course, using suitable bit-masking you *can* address individual bits, but the hardware instructions themselves typically work with all 32/64 bits at once. Here's a simple example. Suppose you have 3 bits you want to store. Since the machine doesn't have a 3-bit built-in type, you typically just use the next larger available size, either a ubyte (8 bits) if you want compact storage, or if compactness isn't a big issue just a uint (32 bits, you just ignore the other 29 bits that you don't need). So you'd declare the storage something like this: uint myBits; Bits are usually indexed from 0, so bit 0 is the first position, bit 1 is the second position, and so on. So to set the first bit to 1, you'd do: myBits |= 0b001; Note that at the machine level, this operator works on all 32 bits at the same time. Most of the bits remain unchanged, though, because bitwise OR does not change the original value if the operand is 0. So the overall effect is that the first bit is set. To set the first bit to 0, there isn't a direct operator that does that, but you can take advantage of the behaviour of bitwise AND, in which any bit which is 0 in the operand will get cleared, everything else remains unchanged. So you'd do this: myBits &= 0b110; Now, since we don't really care about the other 29 bits, we could write this as follows instead, to make our intent clearer: myBits &= ~0b001; The ~ operator flips all the bits, so this is equivalent to writing: myBits &= ~0b_______1110; Writing it with ~ also has the advantage that should we later decide to add another bit to our "bit array", we don't have to update the code; whereas if we'd used `myBits &= 0b110;` then we'd need to change it to `myBits &= 0b1110;` otherwise our new 4th bit may get unexpectedly cleared when we only wanted to clear the first bit. Now, what if we wanted to set both the 1st and 3rd bits? In a hypothetical bit array implementation, we'd do the equivalent of: bool[3] myBits; myBits[0] = 1; myBits[2] = 1; However, in our uint approach, we can cut the number of operations by half, because the CPU is already operating on the entire 32 bits of the uint at once -- so there's no need to have two instructions to set two individual bits when we could just do it all in one: myBits |= 0b101; // look, ma! both bits set at once! Similarly, to clear the 1st and 3rd bits simultaneously, we simply write: myBits &= ~0b101; // clear both bits in 1 instruction! Of course, when we only have 3 bits to work with, the savings isn't that significant. However, if you have a larger bit array, say you need an array of 32 bits, this can speed your code up by 32x, because you're taking advantage of the fact that the hardware is already operating on all 32 bits at the same time. On 64-bit CPUs, you can speed it up by 64x because the CPU operates on all 64 bits simultaneously, so you can manipulate an entire array of 64 bits in a single instruction, which is 64x faster than if you looped over an array of bool with 64 iterations. T -- Without outlines, life would be pointless.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Friday, 15 March 2024 at 17:25:09 UTC, Daniel N wrote:
On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray
wrote:
I am in need of a data type for holding direction information;
one of 8 directions on a single axis. They are named in terms
of compass directions. If D had a 4-bit datatype, I would just
use this and do `+=2` whenever I want to change the datatype,
but it doesn't.
Perhaps this would be a good programming challenge for someone
more experienced than me. Make a data type (probably a struct)
for holding one of 8 directional values using 3 bits. It
should accept the use of increment operators to change the
angle.
Ideally (but optionally), it should work as an enum of the
same name; "Direction".
Here's a unittest that it should ideally pass:
D actually supports both 3 and 4 bit integers. People will
likely warn you of minor portability risks... but if you target
a limited amount of platforms and prefer concise readable code,
then it's a text book example for bitfields. The risk can
easily be mitigated by having an unittest to catch the error
directly(if you try to port to some exotic platform).
dmd -preview=bitfields
(Some lines stolen from Rikki)
```d
struct Direction
{
private uint value : 3;
alias this = value;
enum Direction N = Direction(0);
enum Direction NE = Direction(1);
enum Direction E = Direction(2);
enum Direction SE = Direction(3);
enum Direction S = Direction(4);
enum Direction SW = Direction(5);
enum Direction W = Direction(6);
enum Direction NW = Direction(7);
}
```
Oh wow! That looks so clean and elegant, aside from the `: 3`
part being easy to miss, and not very readable for those not
aware of this feature. This would be so simple. If I used this, I
wouldn't even need to make a struct and write the operator
overload functions; just make an enum for a 3-bit uint.
Based on the words in the command and a quick search, I'm
guessing that this is an experimental feature that has not yet
been accepted as part of the language. Perhaps I shouldn't use
this then, just in case it gets pulled and someone who discovers
my project in the future will have a build error that they don't
know how to solve. This seems like a bigger problem than the
extra memory the current ubyte version takes up, which is
probably quite small for a computer of today anyway.
I suppose this would be a nice feature for the language to have
if the syntax were reworked. Perhaps something like `uint!3
value;` would be better.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Friday, 15 March 2024 at 00:21:42 UTC, H. S. Teoh wrote: On Thu, Mar 14, 2024 at 11:39:33PM +, Liam McGillivray via Digitalmars-d-learn wrote: [...] I tried to rework the functions to use bitwise operations, but it was difficult to figure out the correct logic. I decided that it's not worth the hassle, so I just changed the value storage from `bool[3]` to `ubyte`. [...] Just wanted to note that while in theory bool[3] could be optimized by the compiler for compact storage, what you're most likely to get is 3 bytes, one for each bool, or perhaps even 3 ints (24 bytes). When dealing with units of data smaller than a byte, you generally need to do it manually, because memory is not addressable by individual bits, making it difficult to implement things like slicing an array of bool. So the compiler is most likely to simplify things by making it an array of bytes rather than emit complex bit manipulation code to make up for the lack of bit-addressability in the underlying hardware. Using bit operators like others have pointed out in this thread is probably the best way to implement what you want. T I'm curious as to what "manual implementation" would mean, since clearly making my own struct with `bool[3]` doesn't count. Does D have features for precise memory manipulation? Anyway, I'm surprised that D has a special operator `&=` for doing bit manipulation on integers, especially given that the steps to convert an int into a bool array is more complicated. I would imagine the former would be a rather niche thing.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray wrote:
I am in need of a data type for holding direction information;
one of 8 directions on a single axis. They are named in terms
of compass directions. If D had a 4-bit datatype, I would just
use this and do `+=2` whenever I want to change the datatype,
but it doesn't.
Perhaps this would be a good programming challenge for someone
more experienced than me. Make a data type (probably a struct)
for holding one of 8 directional values using 3 bits. It should
accept the use of increment operators to change the angle.
Ideally (but optionally), it should work as an enum of the same
name; "Direction".
Here's a unittest that it should ideally pass:
D actually supports both 3 and 4 bit integers. People will likely
warn you of minor portability risks... but if you target a
limited amount of platforms and prefer concise readable code,
then it's a text book example for bitfields. The risk can easily
be mitigated by having an unittest to catch the error directly(if
you try to port to some exotic platform).
dmd -preview=bitfields
(Some lines stolen from Rikki)
```d
struct Direction
{
private uint value : 3;
alias this = value;
enum Direction N = Direction(0);
enum Direction NE = Direction(1);
enum Direction E = Direction(2);
enum Direction SE = Direction(3);
enum Direction S = Direction(4);
enum Direction SW = Direction(5);
enum Direction W = Direction(6);
enum Direction NW = Direction(7);
}
```
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Thu, Mar 14, 2024 at 11:39:33PM +, Liam McGillivray via Digitalmars-d-learn wrote: [...] > I tried to rework the functions to use bitwise operations, but it was > difficult to figure out the correct logic. I decided that it's not > worth the hassle, so I just changed the value storage from `bool[3]` > to `ubyte`. [...] Just wanted to note that while in theory bool[3] could be optimized by the compiler for compact storage, what you're most likely to get is 3 bytes, one for each bool, or perhaps even 3 ints (24 bytes). When dealing with units of data smaller than a byte, you generally need to do it manually, because memory is not addressable by individual bits, making it difficult to implement things like slicing an array of bool. So the compiler is most likely to simplify things by making it an array of bytes rather than emit complex bit manipulation code to make up for the lack of bit-addressability in the underlying hardware. Using bit operators like others have pointed out in this thread is probably the best way to implement what you want. T -- LINUX = Lousy Interface for Nefarious Unix Xenophobes.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Friday, 15 March 2024 at 00:00:01 UTC, Richard (Rikki) Andrew Cattermole wrote: On 15/03/2024 12:47 PM, Basile B. wrote: On Thursday, 14 March 2024 at 23:39:33 UTC, Liam McGillivray wrote: On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki) Andrew Cattermole wrote: [...] I tried to rework the functions to use bitwise operations, but it was difficult to figure out the correct logic. I decided that it's not worth the hassle, so I just changed the value storage from `bool[3]` to `ubyte`. Now it works much more like your version. https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d I did a little reading, so now I understand what it means when you have `&= 7`. But I want to ask, is this faster than `%= 8`? If not, I would like to change it to the latter for readability. `%=8` will be codegened using slower intructions w/o optimz enabled but with `&=7` you directly get the right instruction, which does not involves integer division. See https://godbolt.org/z/74vbba5aG Yes, it'll depend upon how smart the compiler is at optimizing and it may not occur in non-optimizing builds. Indeed GDC (so very likely GCC too, or whatever language uses it as backend...) does it without optimz (https://godbolt.org/z/Ke7c54Gqj). That's not very surprising. If you look at LLVM bug tracker, for the tag "missed optimisations", in the report body you'll see a lot of "GDC does that but we dont", even if here it's a bit different, as optimz are not enabled.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On 15/03/2024 12:47 PM, Basile B. wrote: On Thursday, 14 March 2024 at 23:39:33 UTC, Liam McGillivray wrote: On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki) Andrew Cattermole wrote: [...] I tried to rework the functions to use bitwise operations, but it was difficult to figure out the correct logic. I decided that it's not worth the hassle, so I just changed the value storage from `bool[3]` to `ubyte`. Now it works much more like your version. https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d I did a little reading, so now I understand what it means when you have `&= 7`. But I want to ask, is this faster than `%= 8`? If not, I would like to change it to the latter for readability. `%=8` will be codegened using slower intructions w/o optimz enabled but with `&=7` you directly get the right instruction, which does not involves integer division. See https://godbolt.org/z/74vbba5aG Yes, it'll depend upon how smart the compiler is at optimizing and it may not occur in non-optimizing builds. The modulas instructions are based upon division, this is an incredibly expensive operation. https://stackoverflow.com/a/8022107 The division instruction on Haswell for integers ranges from 9 cycles for 8bit, all the way up to 36 cycles for 64bit.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Thursday, 14 March 2024 at 23:39:33 UTC, Liam McGillivray wrote: On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki) Andrew Cattermole wrote: [...] I tried to rework the functions to use bitwise operations, but it was difficult to figure out the correct logic. I decided that it's not worth the hassle, so I just changed the value storage from `bool[3]` to `ubyte`. Now it works much more like your version. https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d I did a little reading, so now I understand what it means when you have `&= 7`. But I want to ask, is this faster than `%= 8`? If not, I would like to change it to the latter for readability. `%=8` will be codegened using slower intructions w/o optimz enabled but with `&=7` you directly get the right instruction, which does not involves integer division. See https://godbolt.org/z/74vbba5aG
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Thursday, 14 March 2024 at 01:58:46 UTC, Richard (Rikki) Andrew Cattermole wrote: The cost of an add + increment then a bitwise and is only 2-4 cycles on a Haswell cpu. Depending upon if its working solely in registers (via inlining) or its operating on ram. Whereas if you need to do branching (if statement, loops), this is an unpredictable cost and loops where a simple bitwise operation can be done is out right non-optimized. As for exceptions, totally not required. You can solve this by simply making your state private so nobody else can mutate it. Bounds checking will ensure if the state is corrupted it'll error out if you use the lookup method I suggested above. I tried to rework the functions to use bitwise operations, but it was difficult to figure out the correct logic. I decided that it's not worth the hassle, so I just changed the value storage from `bool[3]` to `ubyte`. Now it works much more like your version. https://github.com/LiamM32/Open_Emblem/blob/c2014ab3f77e89c0cedcd6dbf7f8362ebfac33a9/source/common.d I did a little reading, so now I understand what it means when you have `&= 7`. But I want to ask, is this faster than `%= 8`? If not, I would like to change it to the latter for readability.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
There appears to be a few things that you may not be aware of based upon this implementation. The cost of an add + increment then a bitwise and is only 2-4 cycles on a Haswell cpu. Depending upon if its working solely in registers (via inlining) or its operating on ram. The cost of a move from ram into a register is about 1 cycle, but can have latencies around 3 cycles if not cached. Whereas if you need to do branching (if statement, loops), this is an unpredictable cost and loops where a simple bitwise operation can be done is out right non-optimized. As for methods like to: ```d static immutable string[] table = ["north", ...]; return table[this.value]; ``` That's two moves from ram to register. In essence in your design, you have blown out the cost by a significant margin well beyond the 12% that is described as being the minimum to consider optimization. If you want to understand where the 12% number comes from I suggest reading the paper "Structured Programming with go to Statements" by Donald Knuth. As for exceptions, totally not required. You can solve this by simply making your state private so nobody else can mutate it. Bounds checking will ensure if the state is corrupted it'll error out if you use the lookup method I suggested above. Understanding what I have said is very important for game engine programmers. So if you're interested in it beyond some hobbyist endeavors you have some reading up to do ;)
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Tuesday, 12 March 2024 at 06:38:28 UTC, Richard (Rikki) Andrew
Cattermole wrote:
By taking advantage of integer wrapping and a bitwise and, its
quite a simple problem to solve!
Challenge for the reader: add support for binary operations and
toString support.
Last night I pushed the latest commit to the GitHub repository
for my game. It contains the `Direction` struct in
[`source/common.d`](https://github.com/LiamM32/Open_Emblem/blob/master/source/common.d). Here it is:
```
struct Direction //One of 8 directions stored in 3 bits
{
import std.conv;
import std.traits: isNumeric;
bool[3] b;
static Direction N = Direction(b:[false,false,false]);
static Direction NE = Direction(b:[true,false,false]);
static Direction E = Direction(b:[false,true,false]);
static Direction SE = Direction(b:[true,true,false]);
static Direction S = Direction(b:[false,false,true]);
static Direction SW = Direction(b:[true,false,true]);
static Direction W = Direction(b:[false,true,true]);
static Direction NW = Direction(b:[true,true,true]);
ref Direction opUnary(string op)() if (op == "++" || op ==
"--") {
static if (op == "++") const bool up = true;
else const bool up = false;
if (b[0]) {
if (b[1]) b[2] = !b[2];
b[1] = !b[1];
}
b[0] = !b[0];
return this;
}
void opOpAssign(string op)(int amount) if (op == "+" || op ==
"-") {
amount = amount%8;
if (amount > 0) for (uint i = 0; i < amount; i++) {
static if (op=="+") this++;
else this--;
} else for (uint i=0; i > amount; i--) {
static if (op=="+") this--;
else this++;
}
}
T to(T)() const if(isNumeric!T) {
return cast(T)(b[0] + 2*b[1] + 4*b[2]);
}
T opCast(T)() if (isNumeric!T) {
return cast(T)(b[0] + 2*b[1] + 4*b[2]);
}
T to(T)() const if(is(T==string)) {
if (this==Direction.N) return "north";
else if (this==Direction.NE) return "northeast";
else if (this==Direction.E) return "east";
else if (this==Direction.SE) return "southeast";
else if (this==Direction.S) return "south";
else if (this==Direction.SW) return "southwest";
else if (this==Direction.W) return "west";
else if (this==Direction.NW) return "northwest";
else throw new Exception("Direction.to!: direction has a
value that should be impossible.");
//else return ""; //This should never happen.
}
bool[3] opCast() const {
return this.b;
}
Direction opposite() const {
return Direction([b[0], b[1], !b[2]]);
}
bool diagonal() {
return b[0];
}
int getAngle() {
if (this==Direction.N) return 0;
else if (this==Direction.NE) return 45;
else if (this==Direction.E) return 90;
else if (this==Direction.SE) return 135;
else if (this==Direction.S) return 180;
else if (this==Direction.SW) return 225;
else if (this==Direction.W) return 270;
else if (this==Direction.NW) return 315;
else throw new Exception("Direction.getAngle: direction
has a value that should be impossible.");
}
}
```
The one thing that cant be done on this is doing `direction+8`.
Perhaps it would have been easier if I had chosen to store the
value as a ubyte rather than an array of bools. While this is
probably over-optimized given the large amount of memory in
today's computers, I like it that it can never be an illegitimate
value.
There's probably some trick I can use to make it easier to figure
out the functions to do numerical operations on bits, but I don't
know how best to cleanly represent this kind of thing in code.
Maybe I need to look for examples of how it's already done.
I noticed among the options for overloading unary operations are
the symbols "+" & "-". What operation is being overloaded with
the function `ref Direction opUnary(string op:"+")(int amount)`?
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Wednesday, 13 March 2024 at 10:27:49 UTC, Basile B. wrote:
The semantics of the operators are actually not as clear as
that. What if you define
```d
enum Direction
{
N = 1, NE, S = 45, SW
}
```
?
Certainly! EnumMembers; can be used. The EnumMembers template
from the std.traits module is used to retrieve all the members of
an enumeration. It generates a tuple containing all the
enumeration values, which can be iterated over using a foreach
loop. In the D programming language, you can use EnumMembers to
iterate over enum values at compile time, which is useful for
generating code based on enum members.
Here’s a simple code example:
```d
enum Days
{
Monday= 1001,
Tuesday = 1010,
Wednesday = 1011,
Thursday = 1100,
Friday= 1101,
Saturday = 1110,
Sunday=
}
import std.traits : EnumMembers;
foreach(day; EnumMembers!Days)
day.writeln(":", cast(int)day);
```
SDB@79
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray wrote:
I am in need of a data type for holding direction information;
one of 8 directions on a single axis. They are named in terms
of compass directions. If D had a 4-bit datatype, I would just
use this and do `+=2` whenever I want to change the datatype,
but it doesn't.
Perhaps this would be a good programming challenge for someone
more experienced than me. Make a data type (probably a struct)
for holding one of 8 directional values using 3 bits. It should
accept the use of increment operators to change the angle.
Ideally (but optionally), it should work as an enum of the same
name; "Direction".
Here's a unittest that it should ideally pass:
```
unittest
{
Direction direction = Direction.N;
direction++;
assert(direction == Direction.NE);
direction+=3;
assert(direction == Direction.S);
direction--;
assert(direction == Direction.SE);
direction-=4;
assert(direction == Direction.NW);
}
```
While there are workarounds (as proposed in the other answers,
using operator overloads) I tend to think that the way currently
enums work with arithmetic operators is a symptom of an
incomplete type-system. Enums made of integer numbers are sub
classes of the parent [integral
sequence](https://en.wikipedia.org/wiki/Integer_sequence).
The semantics of the operators are actually not as clear as that.
What if you define
```d
enum Direction
{
N = 1, NE, S = 45, SW
}
```
?
You directly see that the proposed workarounds dont work anymore.
There are natural numbers, sub-sets of natural numbers, unordered
sequences, etc.
The type system does not represent that. Anyway, I dont blame D,
plenty of languages have the exact same problem.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Tuesday, 12 March 2024 at 05:38:03 UTC, Liam McGillivray wrote:
Perhaps this would be a good programming challenge for someone
more experienced than me. Make a data type (probably a struct)
for holding one of 8 directional values using 3 bits. It should
accept the use of increment operators to change the angle.
D is such a perfect language that you can do the features you
mentioned and more. I also implemented the following during my
rookie years:
```d
alias Direction = enumSet;
union enumSet(T)
{
T e;
alias e this;
struct
{
int i;
auto opUnary(string op: "++")()
=> i = i < e.max ? ++i : e.min;
auto opUnary(string op: "--")()
=> i = i > e.min ? --i : e.max;
auto opOpAssign(string op: "+")(int val)
{
i += val;
if(i > e.max) i -= e.max + 1;
}
auto opOpAssign(string op: "-")(int val)
{
i -= val;
if(i < e.min) i += e.max + 1;
}
}
string toString() const
=> e.to!string;
}
unittest
{
auto direction = Direction!Directions(Directions.N);
direction++;
assert(direction == Directions.NE);
direction+=3;
assert(direction == Directions.S);
direction--;
assert(direction == Directions.SE);
direction-=4;
assert(direction == Directions.NW);
}
import std.stdio, std.conv;
void main()
{
enum Directions
{
N , NE , E, SE, S, SW , W, NW
}
auto test = enumSet!Directions(Directions.W);
test += 9; /*
++test; ++test; ++test;
++test; ++test; ++test;
++test; ++test; ++test;//*/
test.writeln;
test--; test--;
test.writeln;
}
```
Here union was used with an extra template parameter. I also
added 2 aliases to avoid confusion.
SDB@79
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On 13/03/2024 11:00 AM, Liam McGillivray wrote: I'm not familiar with the syntax of the line |value &= 7;|. Is it equivalent to writing |value = value % 7;|? & is a bitwise and. LSB 123456789 MSB & 7 LSB 12300 MSB Anyway, you used an int, but I used an array of 3 bools. I'm guessing that mine uses less memory, but I'm not sure how memory it adds when it's a struct with functions. Due to alignment, it'll probably use just as much. Mine only needs a single ``byte``, at 7 bits it's more than enough. But ``int`` doesn't make much difference unless you are packing instances together ``align(0):`` and realistically cpus are optimized for 32bits not 8.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
On Tuesday, 12 March 2024 at 06:38:28 UTC, Richard (Rikki) Andrew
Cattermole wrote:
By taking advantage of integer wrapping and a bitwise and, its
quite a simple problem to solve!
Challenge for the reader: add support for binary operations and
toString support.
https://dlang.org/spec/operatoroverloading.html
```d
struct Direction {
private int value;
Direction opUnary(string op:"++")() {
value++;
value &= 7;
return this;
}
Direction opUnary(string op:"--")() {
value--;
value &= 7;
return this;
}
void opOpAssign(string op:"+")(int amount) {
value += amount;
value &= 7;
}
void opOpAssign(string op:"-")(int amount) {
value -= amount;
value &= 7;
}
enum Direction N = Direction(0);
enum Direction NE = Direction(1);
enum Direction E = Direction(2);
enum Direction SE = Direction(3);
enum Direction S = Direction(4);
enum Direction SW = Direction(5);
enum Direction W = Direction(6);
enum Direction NW = Direction(7);
}
unittest {
Direction direction = Direction.N;
direction++;
assert(direction == Direction.NE);
direction+=3;
assert(direction == Direction.S);
direction--;
assert(direction == Direction.SE);
direction-=4;
assert(direction == Direction.NW);
}
```
Interesting. I didn't know that an enum can be defined inside a
struct like that. I had used functions to get around it.
Here is what I had already mostly written, using help from
ChatGPT (but only for the opUnary syntax, not the algorithm):
```
struct Direction //One of 8 directions stored in 3 bits
{
bool[3] d;
static Direction N() { return
Direction(d:[false,false,false]); }
static Direction NE() { return
Direction(d:[false,false,true]); }
static Direction E() { return
Direction(d:[false,true,false]); }
static Direction SE() { return
Direction(d:[false,true,true]); }
static Direction S() { return
Direction(d:[true,false,false]); }
static Direction SW() { return
Direction(d:[true,false,true]); }
static Direction W() { return Direction(d:[true,true,false]);
}
static Direction NW() { return Direction(d:[true,true,true]);
}
ref Direction opUnary(string op)() if (op == "++" || op ==
"--") {
if (op == "++") const bool up = true;
else const bool up = false;
if (d[0]) {
if (d[1]) d[2] = !d[2];
d[1] = !d[1];
}
d[0] = !d[0];
return this;
}
auto to(T)() const {
return cast(T)(d[0] + 2*d[1] + 4*d[2]);
}
}
```
I am not entirely sure how well it works. I will come back later
with an updated version with more functions.
I'm not familiar with the syntax of the line `value &= 7;`. Is it
equivalent to writing `value = value % 7;`?
Anyway, you used an int, but I used an array of 3 bools. I'm
guessing that mine uses less memory, but I'm not sure how memory
it adds when it's a struct with functions.
Re: Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
By taking advantage of integer wrapping and a bitwise and, its quite a
simple problem to solve!
Challenge for the reader: add support for binary operations and toString
support.
https://dlang.org/spec/operatoroverloading.html
```d
struct Direction {
private int value;
Direction opUnary(string op:"++")() {
value++;
value &= 7;
return this;
}
Direction opUnary(string op:"--")() {
value--;
value &= 7;
return this;
}
void opOpAssign(string op:"+")(int amount) {
value += amount;
value &= 7;
}
void opOpAssign(string op:"-")(int amount) {
value -= amount;
value &= 7;
}
enum Direction N = Direction(0);
enum Direction NE = Direction(1);
enum Direction E = Direction(2);
enum Direction SE = Direction(3);
enum Direction S = Direction(4);
enum Direction SW = Direction(5);
enum Direction W = Direction(6);
enum Direction NW = Direction(7);
}
unittest {
Direction direction = Direction.N;
direction++;
assert(direction == Direction.NE);
direction+=3;
assert(direction == Direction.S);
direction--;
assert(direction == Direction.SE);
direction-=4;
assert(direction == Direction.NW);
}
```
Challenge: Make a data type for holding one of 8 directions allowing increment and overflow
I am in need of a data type for holding direction information;
one of 8 directions on a single axis. They are named in terms of
compass directions. If D had a 4-bit datatype, I would just use
this and do `+=2` whenever I want to change the datatype, but it
doesn't.
Perhaps this would be a good programming challenge for someone
more experienced than me. Make a data type (probably a struct)
for holding one of 8 directional values using 3 bits. It should
accept the use of increment operators to change the angle.
Ideally (but optionally), it should work as an enum of the same
name; "Direction".
Here's a unittest that it should ideally pass:
```
unittest
{
Direction direction = Direction.N;
direction++;
assert(direction == Direction.NE);
direction+=3;
assert(direction == Direction.S);
direction--;
assert(direction == Direction.SE);
direction-=4;
assert(direction == Direction.NW);
}
```
Re: The One Billion Row Challenge
On Saturday, 13 January 2024 at 23:25:07 UTC, monkyyy wrote: On Thursday, 11 January 2024 at 11:21:39 UTC, Sergey wrote: On Thursday, 11 January 2024 at 08:57:43 UTC, Christian Köstlin wrote: Did someone already try to do this in dlang? I guess it will be very hard to beat the java solutions running with graalvm! https://news.ycombinator.com/item?id=38851337 Kind regards, Christian I think C++ people already beated Java's performance https://github.com/buybackoff/1brc?tab=readme-ov-file#native I feel we could beat c++ if they didn't radix sort The project is very hard. Many optimizations and tricks were applied by others. It requires a lot of skill to implement everything on a high level.
Re: The One Billion Row Challenge
On Thursday, 11 January 2024 at 11:21:39 UTC, Sergey wrote: On Thursday, 11 January 2024 at 08:57:43 UTC, Christian Köstlin wrote: Did someone already try to do this in dlang? I guess it will be very hard to beat the java solutions running with graalvm! https://news.ycombinator.com/item?id=38851337 Kind regards, Christian I think C++ people already beated Java's performance https://github.com/buybackoff/1brc?tab=readme-ov-file#native I feel we could beat c++ if they didn't radix sort
Re: The One Billion Row Challenge
On Thursday, 11 January 2024 at 08:57:43 UTC, Christian Köstlin wrote: Did someone already try to do this in dlang? I guess it will be very hard to beat the java solutions running with graalvm! https://news.ycombinator.com/item?id=38851337 Kind regards, Christian The problem with this challenge can be seen in the initial comments. Writing the fastest possible program *for a specific dataset* is not the same thing as writing the fastest program for an arbitrary dataset of that size. And, indeed, the fastest program is the one that does nothing but print the answer. Speed on this task doesn't tell you anything about performance with different types/sizes of data or constraints on programmer time needed to produce a correct implementation and maintain it over time.
Re: The One Billion Row Challenge
On Thursday, 11 January 2024 at 08:57:43 UTC, Christian Köstlin wrote: Did someone already try to do this in dlang? I guess it will be very hard to beat the java solutions running with graalvm! https://news.ycombinator.com/item?id=38851337 Kind regards, Christian I think C++ people already beated Java's performance https://github.com/buybackoff/1brc?tab=readme-ov-file#native
Re: Threading challenge: calculate fib(45) while spinning
On Friday, 15 October 2021 at 03:35:44 UTC, jfondren wrote:
The book, "The Go Programming Language" has this simple
goroutine example:
[...]
Here is a similar implementation using the concurrency library:
```d
import concurrency;
import concurrency.stream;
import concurrency.sender : justFrom;
import concurrency.operations : via, race;
import concurrency.thread : ThreadSender;
import core.time : msecs;
import std.stdio : writef, writefln, stdout;
import core.thread : Thread;
void main() @safe {
enum chars = `-\|/`;
auto spinner = infiniteStream(0)
.scan((int acc, int _) => acc + 1, 0)
.collect((int i) shared @trusted {
writef("\r%c", chars[i % chars.length]);
stdout.flush();
Thread.sleep(100.msecs);
})
.via(ThreadSender());
enum n = 45;
auto work = justFrom(() => fib(n));
auto result = race(spinner, work).syncWait.value;
writefln("\rFibonacci(%d) = %d", n, result.get);
}
int fib(int x) pure @safe @nogc {
if (x < 2)
return x;
return fib(x - 1) + fib(x - 2);
}
```
Go has language support so it is a bit unfair to compare it.
But this code will properly handle errors (in case `writef` or
`flush` throws), and as well as having an explicit
synchronization point so that the final `writeln` is always after
the spinner is done.
Re: Threading challenge: calculate fib(45) while spinning
On 10/15/21 10:01 AM, Ali Çehreli wrote: > writefln!"\rFibonacci(%d) = %d"(n, fibN); That '\r' bothered me because the actual work needs to know what the spinner is doing to clear its remaining character. I would expect the original go code had the same problem. -Steve
Re: Threading challenge: calculate fib(45) while spinning
On 10/14/21 8:54 PM, Ali Çehreli wrote:
>writefln!"\rFibonacci(%d) = %d"(n, fibN);
That '\r' bothered me because the actual work needs to know what the
spinner is doing to clear its remaining character.
>receiveTimeout(delay,
> (OwnerTerminated msg) {
And there is a race condition because the spinner can print an extra
character by the time it receives the OwnerTerminated message. (You can
observe this by adding e.g. Thread.sleep(300.msecs) after the
"\rFibonnacci..." line above.)
So, I improved it by removing both of those concerns as well as adding
the following:
- An optional message when spinning (it can be further improved because
there is an extra space character if the message is empty)
- A withSpinner() function to work with any delegate
The only requirement is that the delegate should not output to stdout if
we want a clean output.
import std.stdio : stdout, writef, writefln;
import std.concurrency : receiveTimeout, send, spawn;
import std.traits : ReturnType;
import core.thread : Duration, msecs, Thread;
import std.range : cycle, repeat, walkLength;
import std.format : format;
void main() {
enum n = 45;
int fibN; // Left mutable not to complicate the example
withSpinner({
fibN = fib(n); // slow
},
format!"Calculating fib(%s)"(n));
writefln!"Fibonacci(%d) = %d"(n, fibN);
}
// The delegate 'dg' should not output to stdout.
void withSpinner(Dg)(Dg dg,
string message = null,
Duration delay = 100.msecs) {
shared(bool) spinnerDone = false;
auto s = spawn(, message, delay, );
// Do work while spinning
dg();
// Tell the spinner to stop (the value does not matter)
s.send(0x0FF);
// Busy(ish) wait until the spinner is done
while (!spinnerDone) {
Thread.yield();
}
}
void spinner(string message,
Duration delay,
shared(bool) * done) {
foreach (c; `-\|/`.cycle) {
if (receiveTimeout(delay, (int _) {})) {
// Stop request received
// Clear the spinning message
writef("\r%s \r", " ".repeat(walkLength(message)));
// Tell the user we are done
*done = true;
return;
}
writef!"\r%s %c"(message, c);
stdout.flush();
}
}
auto fib(int x) {
if (x < 2) {
return x;
}
return fib(x-1) + fib(x-2);
}
Ali
Re: Threading challenge: calculate fib(45) while spinning
On 10/14/21 11:35 PM, jfondren wrote:
The book, "The Go Programming Language" has this simple goroutine example:
```go
func main() {
go spinner(100 * time.Millisecond)
const n = 45
fibN := fib(n) // slow
fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}
func spinner(delay time.Duration) {
for {
for _, r := range `-\|/` {
fmt.Printf("\r%c", r)
time.Sleep(delay)
}
}
}
func fib(x int) int {
if x < 2 {
return x
}
return fib(x-1) + fib(x-2)
}
```
Attempt #1, with std.concurrency:
```d
import std.concurrency : spawn;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;
void main() @safe {
(() @trusted { spawn(, 100.msecs); })();
const n = 45;
const fibN = fib(n); // slow
writefln!"\rFibonacci(%d) = %d"(n, fibN);
}
void spinner(Duration delay) @safe {
(() @trusted { Thread.getThis.isDaemon(true); })();
while (true) {
foreach (char c; `-\|/`) {
writef!"\r%c"(c);
(() @trusted { stdout.flush; })();
(() @trusted { Thread.sleep(delay); })();
}
}
}
int fib(int x) pure @safe @nogc {
if (x < 2)
return x;
return fib(x - 1) + fib(x - 2);
}
```
This version has two problems:
1. a race condition with `isDaemon`: if `main()` ends before
`isDaemon(true)` is called, then the program never ends because the
kill-non-daemon-threads module destructor is called while the new thread
isn't a daemon thread.
You can also just spawn a thread directly with `Thread`, which I believe
allows you to set the daemon-ness from `main`.
2. it crashes about 10% of the time on exit (in dmd, gdc, and ldc).
valgrind on a gdc build complains about "Conditional jump or move
depends on uninitialised value(s)" early on.
The crash is likely because you are using D i/o utilities, and the
runtime is shut down. Technically it shouldn't cause a problem, but
possibly there are things that are needed deep inside `writef`.
If you switch to `printf`, it will probably work.
-Steve
Re: Threading challenge: calculate fib(45) while spinning
On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:
On 10/14/21 8:35 PM, jfondren wrote:
[...]
Here is one that uses receiveTimeout and OwnerTerminated:
import std.stdio;
import std.concurrency;
import core.thread;
void main() {
spawnLinked(, 100.msecs);
enum n = 45;
const fibN = fib(n); // slow
writefln!"\rFibonacci(%d) = %d"(n, fibN);
}
void spinner(const(Duration) delay) {
for (;;) {
foreach (r; `-\|/`) {
writef!"\r%c"(r);
stdout.flush();
bool done;
receiveTimeout(delay,
(OwnerTerminated msg) {
done = true;
});
if (done) {
return;
}
}
}
}
auto fib(int x) {
if (x < 2) {
return x;
}
return fib(x-1) + fib(x-2);
}
Ali
This is a "similar" approach to what Erlang does. I have always
liked it ☀️
Re: Threading challenge: calculate fib(45) while spinning
On 10/14/21 9:17 PM, jfondren wrote:
On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote:
On 10/14/21 8:35 PM, jfondren wrote:
The book, "The Go Programming Language" has this simple goroutine
example:
Here is one that uses receiveTimeout and OwnerTerminated:
Very nice, replacing Thread.sleep with receiveTimeout and getting
graceful interruption for free. This also doesn't crash.
Cool. :)
Actually, it can be shorter by checking the return value of receiveTimeout:
if (receiveTimeout(delay, (OwnerTerminated msg) {})) {
return;
}
I didn't use this method earlier because I was afraid an unexpected
message might make receiveTimeout return 'true'. But I've tested just
now: Only the expected OwnerTerminated makes it return 'true'.
Ali
Re: Threading challenge: calculate fib(45) while spinning
On Friday, 15 October 2021 at 03:54:17 UTC, Ali Çehreli wrote: On 10/14/21 8:35 PM, jfondren wrote: The book, "The Go Programming Language" has this simple goroutine example: Here is one that uses receiveTimeout and OwnerTerminated: Very nice, replacing Thread.sleep with receiveTimeout and getting graceful interruption for free. This also doesn't crash.
Re: Threading challenge: calculate fib(45) while spinning
On 10/14/21 8:35 PM, jfondren wrote:
The book, "The Go Programming Language" has this simple goroutine example:
Here is one that uses receiveTimeout and OwnerTerminated:
import std.stdio;
import std.concurrency;
import core.thread;
void main() {
spawnLinked(, 100.msecs);
enum n = 45;
const fibN = fib(n); // slow
writefln!"\rFibonacci(%d) = %d"(n, fibN);
}
void spinner(const(Duration) delay) {
for (;;) {
foreach (r; `-\|/`) {
writef!"\r%c"(r);
stdout.flush();
bool done;
receiveTimeout(delay,
(OwnerTerminated msg) {
done = true;
});
if (done) {
return;
}
}
}
}
auto fib(int x) {
if (x < 2) {
return x;
}
return fib(x-1) + fib(x-2);
}
Ali
Threading challenge: calculate fib(45) while spinning
The book, "The Go Programming Language" has this simple goroutine
example:
```go
func main() {
go spinner(100 * time.Millisecond)
const n = 45
fibN := fib(n) // slow
fmt.Printf("\rFibonacci(%d) = %d\n", n, fibN)
}
func spinner(delay time.Duration) {
for {
for _, r := range `-\|/` {
fmt.Printf("\r%c", r)
time.Sleep(delay)
}
}
}
func fib(x int) int {
if x < 2 {
return x
}
return fib(x-1) + fib(x-2)
}
```
Attempt #1, with std.concurrency:
```d
import std.concurrency : spawn;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;
void main() @safe {
(() @trusted { spawn(, 100.msecs); })();
const n = 45;
const fibN = fib(n); // slow
writefln!"\rFibonacci(%d) = %d"(n, fibN);
}
void spinner(Duration delay) @safe {
(() @trusted { Thread.getThis.isDaemon(true); })();
while (true) {
foreach (char c; `-\|/`) {
writef!"\r%c"(c);
(() @trusted { stdout.flush; })();
(() @trusted { Thread.sleep(delay); })();
}
}
}
int fib(int x) pure @safe @nogc {
if (x < 2)
return x;
return fib(x - 1) + fib(x - 2);
}
```
This version has two problems:
1. a race condition with `isDaemon`: if `main()` ends before
`isDaemon(true)` is called, then the program never ends because
the kill-non-daemon-threads module destructor is called while the
new thread isn't a daemon thread.
2. it crashes about 10% of the time on exit (in dmd, gdc, and
ldc). valgrind on a gdc build complains about "Conditional jump
or move depends on uninitialised value(s)" early on.
Attempt #2, with std.parallelism:
```d
import std.parallelism : task, taskPool;
import core.thread : Thread;
import std.stdio : writefln, writef, stdout;
import std.datetime : msecs, Duration;
void main() @safe {
auto spin = task!spinner(100.msecs);
taskPool.put(spin);
const n = 45;
const fibN = fib(n); // slow
writefln!"\rFibonacci(%d) = %d"(n, fibN);
}
void spinner(Duration delay) @safe {
while (true) {
foreach (char c; `-\|/`) {
writef!"\r%c"(c);
(() @trusted { stdout.flush; })();
(() @trusted { Thread.sleep(delay); })();
}
}
}
int fib(int x) pure @safe @nogc {
if (x < 2)
return x;
return fib(x - 1) + fib(x - 2);
}
```
This version continues to spin after the Fibonacci result is
printed, despite
https://dlang.org/phobos/std_parallelism.html#.taskPool saying
that `taskPool` worker threads are daemon by default, and despite
various attempts to add `isDaemon(true)` calls.
Is there a d version without these problems, and without varying
substantially from the go (by e.g. having the spinner poll to see
if it should exit gracefully).
Re: Bit rotation question/challenge
On Saturday, 30 January 2021 at 14:56:14 UTC, burt wrote:
On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote:
On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:
On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
[...]
cast as uint and shift. cast the result as ubyte[4].
obiously, that works for n=4 with uint and n=8 for ulong, only.
Yes I used to do this, but then I needed it for n > 8.
You can try somethink like this:
https://run.dlang.io/is/POQgnb
import std.range : cycle, take, drop;
import std.algorithm : copy;
import std.stdio;
version (LittleEndian)
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint
rotation){
typeof(return) result;
array[]
.cycle()
.drop(n - (rotation / 8) % n)
.take(n)
.copy(result[]);
const ubyte bit_rotation = rotation % 8;
enum ubyte full = 0b_;
if(bit_rotation == 0)
return result;
ubyte next_prefix(const ubyte elm){
const ubyte suffix = (elm & ~(full << bit_rotation));
const ubyte prefix = cast(ubyte)(suffix << (8 -
bit_rotation));
return prefix;
}
ubyte prefix = next_prefix(result[$-1]);
foreach(ref ubyte elm; result[]){
const new_prefix = next_prefix(elm);
elm = (elm >> bit_rotation) | prefix;
prefix = new_prefix;
}
return result;
}
void main(){
ubyte[4] x = [
0b00011000,
0b0011,
0b00010101,
0b0010,
];
writefln!"%(%8b,\n%)"(x.rotateRight(4));
}
Re: Bit rotation question/challenge
On Saturday, 30 January 2021 at 14:56:14 UTC, burt wrote: On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote: On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote: On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote: [...] cast as uint and shift. cast the result as ubyte[4]. obiously, that works for n=4 with uint and n=8 for ulong, only. Yes I used to do this, but then I needed it for n > 8. As suggested in the other answer BitArray may be the best generic solution.
Re: Bit rotation question/challenge
On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote: On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote: On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote: [...] cast as uint and shift. cast the result as ubyte[4]. obiously, that works for n=4 with uint and n=8 for ulong, only. Yes I used to do this, but then I needed it for n > 8.
Re: Bit rotation question/challenge
On Saturday, 30 January 2021 at 14:17:06 UTC, Paul Backus wrote:
On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
[...]
Now I want to bit-rotate the array as if it is one big integer.
You may find `std.bitmanip.BitArray` useful for this:
http://phobos.dpldocs.info/std.bitmanip.BitArray.html
Thank you, this is indeed what I am looking for!
For future reference, this is how I implemented it:
```d
ubyte[n] rotateRight(size_t n)(ubyte[n] x, uint rotation)
{
import std.bitmanip : BitArray;
ubyte[n] x2;
foreach (i, value; x) // have to swap because of endianness
x2[n - 1 - i] = value;
auto copy = x2;
auto bitArray1 = BitArray(cast(void[]) x2[], n * 8);
auto bitArray2 = BitArray(cast(void[]) copy[], n * 8);
bitArray1 >>= rotation;
bitArray2 <<= n * 8 - rotation;
bitArray1 |= bitArray2;
foreach (i, value; x2) // swap back
x[n - 1 - i] = value;
return x;
}
ubyte[4] x = [
0b00011000,
0b0011,
0b00010101,
0b0010,
];
writefln!"%(%8b,\n%)"(x.rotateRight(4));
```
Re: Bit rotation question/challenge
On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:
On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
I have a static array of `ubyte`s of arbitrary size:
```d
ubyte[4] x = [ // in reality, ubyte[64]
0b1000,
0b0001,
0b00010101,
0b0010,
];
```
Now I want to bit-rotate the array as if it is one big
integer. So:
```d
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint
rotation)
{
// ?
}
// same for rotateLeft
ubyte[4] y = [
0b1001,
0b0100,
0b,
0b10001010,
];
assert(x.rotateRight(9) == y);
assert(y.rotateLeft(9) == x);
```
Any ideas how this could be achieved? I.e. what should go at
the "?" for rotateRight and rotateLeft?
cast as uint and shift. cast the result as ubyte[4].
obiously, that works for n=4 with uint and n=8 for ulong, only.
Re: Bit rotation question/challenge
On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
I have a static array of `ubyte`s of arbitrary size:
```d
ubyte[4] x = [ // in reality, ubyte[64]
0b1000,
0b0001,
0b00010101,
0b0010,
];
```
Now I want to bit-rotate the array as if it is one big integer.
So:
```d
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint
rotation)
{
// ?
}
// same for rotateLeft
ubyte[4] y = [
0b1001,
0b0100,
0b,
0b10001010,
];
assert(x.rotateRight(9) == y);
assert(y.rotateLeft(9) == x);
```
Any ideas how this could be achieved? I.e. what should go at
the "?" for rotateRight and rotateLeft?
cast as uint and shift. cast the result as ubyte[4].
Re: Bit rotation question/challenge
On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote: I have a static array of `ubyte`s of arbitrary size: ```d ubyte[4] x = [ // in reality, ubyte[64] 0b1000, 0b0001, 0b00010101, 0b0010, ]; ``` Now I want to bit-rotate the array as if it is one big integer. You may find `std.bitmanip.BitArray` useful for this: http://phobos.dpldocs.info/std.bitmanip.BitArray.html
Bit rotation question/challenge
I have a static array of `ubyte`s of arbitrary size:
```d
ubyte[4] x = [ // in reality, ubyte[64]
0b1000,
0b0001,
0b00010101,
0b0010,
];
```
Now I want to bit-rotate the array as if it is one big integer.
So:
```d
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint
rotation)
{
// ?
}
// same for rotateLeft
ubyte[4] y = [
0b1001,
0b0100,
0b,
0b10001010,
];
assert(x.rotateRight(9) == y);
assert(y.rotateLeft(9) == x);
```
Any ideas how this could be achieved? I.e. what should go at the
"?" for rotateRight and rotateLeft?
Challenge
I recently came across an interesting exercise.
Given a series of positive numbers, each of which belongs to the
set
{ 2^^i * 3^^j * 5^^k | i, j, k ≥ 0 }.
The series is ordered in ascending order. The beginning looks
like this:
{ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ... }
The goal is to get the Nth element of the series. For example,
for N = 10, the answer is 12.
On the Internet, I found an elegant and incredibly fast solution
in Haskell:
```
mergeUniq :: Ord a => [a] -> [a] -> [a]
mergeUniq (x:xs) (y:ys) = case x `compare` y of
EQ -> x : mergeUniq xs ys
LT -> x : mergeUniq xs (y:ys)
GT -> y : mergeUniq (x:xs) ys
powers :: [Integer]
powers = 1 : expand 2 `mergeUniq` expand 3 `mergeUniq` expand 5
where
expand factor = (factor *) <$> powers
main = print $ powers!!99
```
On my machine, the 100th element is found in 0.215s. OMG!
After that, I spent almost the entire day searching for at least
the same fast solution in D.
My first attempt was simple and quite pretty, but awfully slow:
```
import std.stdio;
import std.array;
import std.bigint;
import std.algorithm;
auto generate(int n) {
BigInt[] nums = [BigInt("1")];
foreach(i; 0..n) {
nums = merge(nums, [nums[i] * 2, nums[i] * 3, nums[i] *
5]).uniq().array();
}
return nums[n - 1];
}
void main() {
writeln(generate(5000));
}
```
0.275s for 5000th element.
At the end of the day, I managed to catch up and even overtake
Haskell by emulating its lazyness with ranges and a funny trick.
Victory! :)
If you find this interesting, I will publish my latest version.
And feel free to find your own solution. ;)
Re: For fun: Expressive C++ 17 Coding Challenge in D
Another solution using dlangs builtin csv support for reading.
import std.csv;
import std.file;
import std.algorithm : map;
import std.range;
string csvWrite(Header, Rows)(Header header, Rows rows)
{
return header.join(",") ~ "\n" ~ rows.map!(r => header.map!(h =>
r[h]).join(",")).join("\n");
}
int main(string[] args)
{
auto inputFile = args[1];
auto columnName = args[2];
auto replacement = args[3];
auto outputFile = args[4];
auto records = readText(inputFile).csvReader!(string[string])(null);
write(outputFile, csvWrite(records.header, records.map!((r) {
r[columnName] = replacement;
return r;
})));
return 0;
}
Unfortunately this is still far from the powershell solution :/
cK
Re: For fun: Expressive C++ 17 Coding Challenge in D
I am a total beginner but I want to post that a lot.
auto autoCorrelation(R)(R range)
if (isRandomAccessRange!R)
{
import std.numeric : fft, inverseFft;
import std.range : chain, repeat, zip, dropBack;
import std.algorithm : map;
import std.complex;
auto residual = residualPowerOf2(range.length);
auto fftResult = range.chain(repeat(0, residual)).fft();
auto autoCorrResult = fftResult.zip(fftResult.map!(a =>
a.conj())).
map!( a=> a[0] * a[1] ).
inverseFft().
dropBack(residual).
map!( a => a.re );
return autoCorrResult;
}
I implemented auto correlation in C++ before which is I believe
2~3 time bigger(also I needed to compile fftw, lapack etc.. ) :
https://forum.kde.org/viewtopic.php?f=74=118619 .
That was the moment I feel in love with D.
Re: For fun: Expressive C++ 17 Coding Challenge in D
On Wednesday, 4 October 2017 at 19:20:12 UTC, Jesse Phillips wrote: On Wednesday, 4 October 2017 at 15:26:02 UTC, Ali Çehreli wrote: On 10/04/2017 02:04 AM, Biotronic wrote: ... Hey where is the list of features used e.g: ranges, ufcs... Features used: D. But sure, added them to the gist: https://gist.github.com/Biotronic/0bc6048b880d67bfdca970453cc47cf9 Also added some more stuff to show off more D features, like unittests and @safe. -- Biotronic
Re: For fun: Expressive C++ 17 Coding Challenge in D
On Wednesday, 4 October 2017 at 15:30:08 UTC, Ali Çehreli wrote:
the hidden \r characters at the ends
Those got me too!
Here's my less than optimal solution:
int main(string[] args)
{ import std.stdio;
import std.algorithm.iteration : map, splitter, joiner, each;
import std.algorithm.searching : countUntil;
import std.range : enumerate;
import std.string : chomp;
if (args.length != 5 && args.length != 4)
{ stderr.writeln("Something went wrong and it's obviously
your fault.");
return 1;
}
immutable columnID = args[2];
immutable substitute = args[3];
auto data = File(args[1], "r").byLine.map!chomp;
if (data.empty)
{ stderr.writeln("input file missing\n\n(actually it
exists, it's just "
~ "empty)\n\n(your fault regardless)");
return 1;
}
File output;
if (args.length == 5)
output = File(args[4], "w");
else
output = stdout;
immutable matchedColumn =
data.front.splitter(",").countUntil(columnID);
if (matchedColumn < 0)
{ stderr.writeln("column name doesn’t exist in the input
file\n\n(and "
~ "it's your fault)");
return 1;
}
output.writeln(data.front);
data.popFront;
data.map!(line => line
.splitter(",")
.enumerate
.map!(a => a.index == matchedColumn ? substitute :
a.value)
.joiner(",")).each!(a => output.writeln(a));
return 0;
}
I think the biggest problem is the lack of support for quoted
content.
Re: For fun: Expressive C++ 17 Coding Challenge in D
On Wednesday, 4 October 2017 at 15:26:02 UTC, Ali Çehreli wrote: On 10/04/2017 02:04 AM, Biotronic wrote: ... Hey where is the list of features used e.g: ranges, ufcs...
Re: For fun: Expressive C++ 17 Coding Challenge in D
On Wednesday, 4 October 2017 at 15:30:08 UTC, Ali Çehreli wrote: On 10/04/2017 02:26 AM, Atila Neves wrote: > in D so trivial it'd probably make me sleep out of boredom. I spent more time on this obviously trivial program than necessary. :( In addition to facing known template resolution issues, the hidden \r characters at the ends of some of the fields in the example textcolumns threw me off for a while. (Compounded by silly mistakes that I was making.) But it's not wasted time. You could also use it somewhere else. Blog post, updated version of your book, new book, etc.
Re: For fun: Expressive C++ 17 Coding Challenge in D
On 10/04/2017 02:26 AM, Atila Neves wrote: > in D so trivial it'd probably make me sleep out of boredom. I spent more time on this obviously trivial program than necessary. :( In addition to facing known template resolution issues, the hidden \r characters at the ends of some of the fields in the example textcolumns threw me off for a while. (Compounded by silly mistakes that I was making.) > Maybe that should be our new catchphrase: > > "D: Making programming boring" While still keeping it interesting enough to scratch your head once in a while. :) Ali
Re: For fun: Expressive C++ 17 Coding Challenge in D
On 10/04/2017 02:04 AM, Biotronic wrote:
> I opted for writing to stdout instead, because 1) it's easier, x) it's
> less code, and b) it's more flexible.
Exactly! :)
> a simple replacement of readText with an mmapped equivalent should
> enable humongous file support with no other code change required.
Here is one from me:
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
const delim = ",";
auto byColumn(R)(R range) {
return range
.splitter(delim)
.map!strip;
}
int main(string[] args) {
if (args.length != 3) {
stderr.writefln("USAGE: %s ", args[0]);
return 1;
}
const columnName = args[1];
auto lines = stdin.byLine;
const columnNumber = lines
.front
.byColumn
.countUntil(columnName);
if (columnNumber == -1) {
stderr.writefln(`ERROR: Failed to find "%s".`, columnName);
return 1;
}
writeln(lines.front);
lines.popFront();
const replacement = args[2];
auto replaced = lines
.map!(line => line
.byColumn
.enumerate
.map!(t => (t[0] == columnNumber) ?
replacement : t[1])
.joiner(delim));
writefln("%(%s\n%)", replaced);
return 0;
}
Ali
Re: For fun: Expressive C++ 17 Coding Challenge in D
On Wednesday, 4 October 2017 at 09:04:58 UTC, Biotronic wrote:
Since the code uses ranges though, a simple replacement of
readText with an mmapped equivalent should enable humongous
file support with no other code change required.
Drop-in replacement for readText:
struct MmText {
import std.mmfile;
ulong _fileOffset;
MmFile _file;
this(string filename) {
_file = new MmFile(filename);
}
dchar front() {
auto end = min(_file.length, _fileOffset+4);
auto data = cast(string)_file[_fileOffset..end];
return decodeFront(data);
}
void popFront() {
auto end = min(_file.length, _fileOffset+4);
auto data = cast(string)_file[_fileOffset..end];
size_t bytes;
decodeFront(data, bytes);
_fileOffset += bytes;
}
bool empty() {
return _fileOffset >= _file.length;
}
}
--
Biotronic
Re: For fun: Expressive C++ 17 Coding Challenge in D
On Tuesday, 3 October 2017 at 19:25:56 UTC, Ali Çehreli wrote: Found on Reddit: https://www.reddit.com/r/programming/comments/740617/the_expressive_c17_coding_challenge/ How would you do it in D? Ali P.S. You can ignore the following note from the challenge text; I don't think it applies to D. Honestly, I don't think it matters for C++17 either. :) "You can assume input files won't be super large and can fit fully into memory." I can't bring myself to code a solution in C++17 or D. In C++17 it'd be too painful, and in D so trivial it'd probably make me sleep out of boredom. Maybe that should be our new catchphrase: "D: Making programming boring" :P Atila
Re: For fun: Expressive C++ 17 Coding Challenge in D
On Tuesday, 3 October 2017 at 19:25:56 UTC, Ali Çehreli wrote: Found on Reddit: https://www.reddit.com/r/programming/comments/740617/the_expressive_c17_coding_challenge/ How would you do it in D? Ali P.S. You can ignore the following note from the challenge text; I don't think it applies to D. Honestly, I don't think it matters for C++17 either. :) "You can assume input files won't be super large and can fit fully into memory." https://gist.github.com/Biotronic/0bc6048b880d67bfdca970453cc47cf9 I opted for writing to stdout instead, because 1) it's easier, x) it's less code, and b) it's more flexible. The memory limitations certainly do apply - readText would fail upon reading humongous files, and for 32-bit programs the resulting string wouldn't be able to hold enough data. Since the code uses ranges though, a simple replacement of readText with an mmapped equivalent should enable humongous file support with no other code change required. -- Biotronic
For fun: Expressive C++ 17 Coding Challenge in D
Found on Reddit: https://www.reddit.com/r/programming/comments/740617/the_expressive_c17_coding_challenge/ How would you do it in D? Ali P.S. You can ignore the following note from the challenge text; I don't think it applies to D. Honestly, I don't think it matters for C++17 either. :) "You can assume input files won't be super large and can fit fully into memory."
Re: For those ready to take the challenge
On Friday, 9 January 2015 at 17:18:43 UTC, Adam D. Ruppe wrote: Huh, looking at the answers on the website, they're mostly using regular expressions. Weaksauce. And wrong - they don't find ALL the links, they find the absolute HTTP urls! Yeah... Surprising, since languages like python includes a HTML parser in the standard library. Besides, if you want all resource links you have to do a lot better, since the following attributes can contain resource addresses: href, src, data, cite, xlink:href… You also need to do entity expansion since the links can contain html entities like amp;. Depressing.
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 15:13:27 UTC, Adam D. Ruppe wrote: On Saturday, 10 January 2015 at 12:34:42 UTC, Tobias Pankrath wrote: Since it is a comparison of languages it's okay to match the original behaviour. I don't think this is really a great comparison of languages either though because it is gluing together a couple library tasks. Only a few bits about the actual language are showing through. In the given regex solutions, C++ has an advantage over C wherein the regex structure can be freed automatically in a destructor and a raw string literal in here, but that's about all from the language itself. The original one is kinda long because he didn't use a http get library, not because the language couldn't do one. There are bits where the language can make those libraries nicer too: dom.d uses operator overloading and opDispatch to support things like .attribute and also .attr.X and .style.foo and element[selector].addClass(foo) and so on implemented in very very little code - I didn't have to manually list methods for the collection or properties for the attributes - ...but a library *could* do it that way and get similar results for the end user; the given posts wouldn't show that. I agree and one of the answers says: I think the no third-party assumption is a fallacy. And is a specific fallacy that afflicts C++ developers, since it's so hard to make reusable code in C++. When you are developing anything at all, even if it's a small script, you will always make use of whatever pieces of reusable code are available to you. The thing is, in languages like Perl, Python, Ruby (to name a few), reusing someone else's code is not only easy, but it is how most people actually write code most of the time. I think he's wrong, because it spoils the comparison. Every answer should delegate those tasks to a library that Stroustroup used as well, e.g. regex matching, string to number conversion and some kind of TCP sockets. But it must do the same work that he's solution does: Create and parse HTML header and extract the html links, probably using regex, but I wouldn't mind another solution. Everyone can put a libdo_the_stroustroup_thing on dub and then call do_the_stroustroup_thing() in main. To compare what the standard libraries (and libraries easily obtained or quasi standard) offer is another challenge.
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 15:52:21 UTC, Tobias Pankrath wrote: ... The thing is, in languages like Perl, Python, Ruby (to name a few), reusing someone else's code is not only easy, but it is how most people actually write code most of the time. I think he's wrong, because it spoils the comparison. Every answer should delegate those tasks to a library that Stroustroup used as well, e.g. regex matching, string to number conversion and some kind of TCP sockets. But it must do the same work that he's solution does: Create and parse HTML header and extract the html links, probably using regex, but I wouldn't mind another solution. Everyone can put a libdo_the_stroustroup_thing on dub and then call do_the_stroustroup_thing() in main. To compare what the standard libraries (and libraries easily obtained or quasi standard) offer is another challenge. I disagree. The great thing about comes with batteries runtimes is that I have the guarantee the desired features exist in all platforms supported by the language. If the libraries are dumped into a repository, there is always a problem if the library works across all OS supported by the language or even if they work together at all. Specially if they depend on common packages with incompatible versions. This is the cause of so many string and vector types across all C++ libraries as most of those libraries were developed before C++98 was even done. Or why C runtime isn't nothing more than a light version of UNIX as it was back in 1989, without any worthwhile feature since then, besides some extra support for numeric types and a little more secure libraries. Nowadays, unless I am doing something very OS specific, I hardly care which OS I am using, thanks to such comes with batteries runtimes. -- Paulo
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 15:52:21 UTC, Tobias Pankrath wrote: I think he's wrong, because it spoils the comparison. Every answer should delegate those tasks to a library that Stroustroup used as well, e.g. regex matching, string to number conversion and some kind of TCP sockets. But it must do the same work that he's solution does: Create and parse HTML header and extract the html links, probably using regex, but I wouldn't mind another solution. The challenge is completely pointless. Different languages have different ways of hacking together a compact incorrect solution. How to directly translate a C++ hack into another language is a task for people who are drunk. For the challenge to make sense it would entail parsing all legal HTML5 documents, extracting all resource links, converting them into absolute form and printing them one per line. With no hickups.
Re: For those ready to take the challenge
On Friday, 9 January 2015 at 17:15:43 UTC, Adam D. Ruppe wrote:
import arsd.dom;
import std.net.curl;
import std.stdio, std.algorithm;
void main() {
auto document = new Document(cast(string)
get(http://www.stroustrup.com/C++.html;));
writeln(document.querySelectorAll(a[href]).map!(a=a.href));
}
Or perhaps better yet:
import arsd.dom;
import std.net.curl;
import std.stdio;
void main() {
auto document = new Document(cast(string)
get(http://www.stroustrup.com/C++.html;));
foreach(a; document.querySelectorAll(a[href]))
writeln(a.href);
}
Which puts each one on a separate line.
Both these code examples triggers the same assert()
dmd: expression.c:3761: size_t StringExp::length(int): Assertion
`encSize == 1 || encSize == 2 || encSize == 4' failed.
on dmd git master. Ideas anyone?
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 17:23:31 UTC, Ola Fosheim Grøstad
wrote:
For the challenge to make sense it would entail parsing all
legal HTML5 documents, extracting all resource links,
converting them into absolute form and printing them one per
line. With no hickups.
Though, that's still a library thing rather than a language thing.
dom.d and the Url struct in cgi.d should be able to do all that,
in just a few lines even, but that's just because I've done a
*lot* of web scraping with the libs before so I made them work
for that.
In fact let me to do it. I'll use my http2.d instead of
cgi.d, actually, it has a similar Url struct just more focused on
client requests.
import arsd.dom;
import arsd.http2;
import std.stdio;
void main() {
auto base = Uri(http://www.stroustrup.com/C++.html;);
// http2 is a newish module of mine that aims to imitate
// a browser in some ways (without depending on curl btw)
auto client = new HttpClient();
auto request = client.navigateTo(base);
auto document = new Document();
// and http2 provides an asynchonous api but you can
// pretend it is sync by just calling waitForCompletion
auto response = request.waitForCompletion();
// parseGarbage uses a few tricks to fixup invalid/broken
HTML
// tag soup and auto-detect character encodings,
including when
// it lies about being UTF-8 but is actually Windows-1252
document.parseGarbage(response.contentText);
// Uri.basedOn returns a new absolute URI based on
something else
foreach(a; document.querySelectorAll(a[href]))
writeln(Uri(a.href).basedOn(base));
}
Snippet of the printouts:
[...]
http://www.computerhistory.org
http://www.softwarepreservation.org/projects/c_plus_plus/
http://www.morganstanley.com/
http://www.cs.columbia.edu/
http://www.cse.tamu.edu
http://www.stroustrup.com/index.html
http://www.stroustrup.com/C++.html
http://www.stroustrup.com/bs_faq.html
http://www.stroustrup.com/bs_faq2.html
http://www.stroustrup.com/C++11FAQ.html
http://www.stroustrup.com/papers.html
[...]
The latter are relative links that it based on and the first few
are absolute. Seems to have worked.
There's other kinds of links than just a[href], but fetching them
is as simple as adding them to the selector or looping for them
too separately:
foreach(a; document.querySelectorAll(script[src]))
writeln(Uri(a.src).basedOn(base));
none on that page, no links either, but it is easy enough to do
with the lib.
Looking at the source of that page, I find some invalid HTML and
lies about the character set. How did Document.parseGarbage do?
Pretty well, outputting the parsed DOM tree shows it
auto-corrected the problems I see by eye.
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 15:52:21 UTC, Tobias Pankrath wrote: But it must do the same work that he's solution does: Create and parse HTML header and extract the html links, probably using regex, but I wouldn't mind another solution. Yeah, that would be best. BTW interesting line here: s GET http://; + server + / + file HTTP/1.0\r\n; s Host: server \r\n; Why + instead of ? C++'s usage of is totally blargh to me anyway, but seeing both is even stranger. Weird language, weird library. Everyone can put a libdo_the_stroustroup_thing on dub and then call do_the_stroustroup_thing() in main. To compare what the standard libraries (and libraries easily obtained or quasi standard) offer is another challenge. Yeah.
Re: For those ready to take the challenge
Adam D. Ruppe: Don't use git master :P Is the issue in Bugzilla? Bye, bearophile
Re: For those ready to take the challenge
Vladimir Panteleev via Digitalmars-d-learn píše v So 10. 01. 2015 v
07:42 +:
On Saturday, 10 January 2015 at 02:10:04 UTC, Jesse Phillips
wrote:
On Friday, 9 January 2015 at 13:50:29 UTC, eles wrote:
https://codegolf.stackexchange.com/questions/44278/debunking-stroustrups-debunking-of-the-myth-c-is-for-large-complicated-pro
Link to answer in D:
http://codegolf.stackexchange.com/a/44417/13362
I think byLine is not necessary. By default . will not match line
breaks.
One statement solution:
import std.net.curl, std.stdio;
import std.algorithm, std.regex;
void main() {
get(http://www.stroustrup.com/C++.html;)
.matchAll(`a.*?href=(.*)`)
.map!(m = m[1])
.each!writeln();
}
Requires Phobos PR#2024 ;)
Oh here is it, I was looking for each. I think it is allready in a
phobos but I can not find. Now I know why :D
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 12:34:42 UTC, Tobias Pankrath wrote: Since it is a comparison of languages it's okay to match the original behaviour. I don't think this is really a great comparison of languages either though because it is gluing together a couple library tasks. Only a few bits about the actual language are showing through. In the given regex solutions, C++ has an advantage over C wherein the regex structure can be freed automatically in a destructor and a raw string literal in here, but that's about all from the language itself. The original one is kinda long because he didn't use a http get library, not because the language couldn't do one. There are bits where the language can make those libraries nicer too: dom.d uses operator overloading and opDispatch to support things like .attribute and also .attr.X and .style.foo and element[selector].addClass(foo) and so on implemented in very very little code - I didn't have to manually list methods for the collection or properties for the attributes - ...but a library *could* do it that way and get similar results for the end user; the given posts wouldn't show that.
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 13:22:57 UTC, Nordlöw wrote: on dmd git master. Ideas anyone? Don't use git master :P Definitely another regression. That line was just pushed to git like two weeks ago and the failing assertion is pretty obviously a pure dmd code bug, it doesn't know the length of char apparently.
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 15:24:45 UTC, bearophile wrote: Is the issue in Bugzilla? https://issues.dlang.org/show_bug.cgi?id=13966
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 15:24:45 UTC, bearophile wrote: Is the issue in Bugzilla? I don't know, bugzilla is extremely difficult to search. I guess I'll post it again and worst case it will be closed as a duplicate.
Re: For those ready to take the challenge
On Friday, 9 January 2015 at 17:18:43 UTC, Adam D. Ruppe wrote: Huh, looking at the answers on the website, they're mostly using regular expressions. Weaksauce. And wrong - they don't find ALL the links, they find the absolute HTTP urls! Since it is a comparison of languages it's okay to match the original behaviour.
Re: For those ready to take the challenge
On Friday, 9 January 2015 at 13:50:29 UTC, eles wrote: https://codegolf.stackexchange.com/questions/44278/debunking-stroustrups-debunking-of-the-myth-c-is-for-large-complicated-pro From the link: Let's show Stroustrup what small and readable program actually is. Alright, there are a lot a examples in many languagens, but those examples doesn't should handle exceptions like the original code does? Matheus.
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 19:17:22 UTC, Ola Fosheim Grøstad wrote: Nice and clean code; does it expand html entities (amp)? Of course. It does it both ways: spana amp;/span span.innerText == a span.innerText = a \ b; assert(span.innerHTML == a quot; b); parseGarbage also tries to fix broken entities, so like standing alone it will translate to amp; for you. there's also parseStrict which just throws an exception in cases like that. That's one thing a lot of XML parsers don't do in the name of speed, but I do since it is pretty rare that I don't want them translated. One thing I did for a speedup though was scan the string for and if it doesn't find one, return a slice of the original, and if it does, return a new string with the entity translated. Gave a surprisingly big speed boost without costing anything in convenience. The HTML5 standard has improved on HTML4 by now being explicit on how incorrect documents shall be interpreted in section 8.2. That ought to be sufficient, since that is what web browsers are supposed to do. http://www.w3.org/TR/html5/syntax.html#html-parser Huh, I never read that, my thing just did what looked right to me over hundreds of test pages that were broken in various strange and bizarre ways.
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 14:56:09 UTC, Adam D. Ruppe wrote: On Saturday, 10 January 2015 at 13:22:57 UTC, Nordlöw wrote: on dmd git master. Ideas anyone? Don't use git master :P Do use git master. The more people do, the fewer regressions will slip into the final release. You can use Dustmite to reduce the code to a simple example, and Digger to find the exact pull request which introduced the regression. (Yes, shameless plug, preaching to the choir, etc.)
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 17:39:17 UTC, Adam D. Ruppe wrote: Though, that's still a library thing rather than a language thing. It is a language-library-platform thing, things like how composable the eco system is would be interesting to compare. But it would be unfair to require a minimalistic language to not use third party libraries. One should probably require that the library used is generic (not a spider-framework), not using FFI, mature and maintained? document.parseGarbage(response.contentText); // Uri.basedOn returns a new absolute URI based on something else foreach(a; document.querySelectorAll(a[href])) writeln(Uri(a.href).basedOn(base)); } Nice and clean code; does it expand html entities (amp)? The HTML5 standard has improved on HTML4 by now being explicit on how incorrect documents shall be interpreted in section 8.2. That ought to be sufficient, since that is what web browsers are supposed to do. http://www.w3.org/TR/html5/syntax.html#html-parser
Re: For those ready to take the challenge
On Saturday, 10 January 2015 at 02:10:04 UTC, Jesse Phillips
wrote:
On Friday, 9 January 2015 at 13:50:29 UTC, eles wrote:
https://codegolf.stackexchange.com/questions/44278/debunking-stroustrups-debunking-of-the-myth-c-is-for-large-complicated-pro
Link to answer in D:
http://codegolf.stackexchange.com/a/44417/13362
I think byLine is not necessary. By default . will not match line
breaks.
One statement solution:
import std.net.curl, std.stdio;
import std.algorithm, std.regex;
void main() {
get(http://www.stroustrup.com/C++.html;)
.matchAll(`a.*?href=(.*)`)
.map!(m = m[1])
.each!writeln();
}
Requires Phobos PR#2024 ;)
Re: For those ready to take the challenge
On Friday, 9 January 2015 at 13:50:29 UTC, eles wrote: https://codegolf.stackexchange.com/questions/44278/debunking-stroustrups-debunking-of-the-myth-c-is-for-large-complicated-pro Link to answer in D: http://codegolf.stackexchange.com/a/44417/13362
Re: For those ready to take the challenge
On 1/9/15 6:10 PM, Jesse Phillips wrote: On Friday, 9 January 2015 at 13:50:29 UTC, eles wrote: https://codegolf.stackexchange.com/questions/44278/debunking-stroustrups-debunking-of-the-myth-c-is-for-large-complicated-pro Link to answer in D: http://codegolf.stackexchange.com/a/44417/13362 Nailed it. -- Andrei
Re: For those ready to take the challenge
Huh, looking at the answers on the website, they're mostly using regular expressions. Weaksauce. And wrong - they don't find ALL the links, they find the absolute HTTP urls!
Re: For those ready to take the challenge
On Friday, 9 January 2015 at 16:55:30 UTC, Justin Whear wrote:
Was excited to give it a try, then remembered...std.xml :(
Well, as the author of my dom.d, I think it counts as a first
party library when I use it!
---
import arsd.dom;
import std.net.curl;
import std.stdio, std.algorithm;
void main() {
auto document = new Document(cast(string)
get(http://www.stroustrup.com/C++.html;));
writeln(document.querySelectorAll(a[href]).map!(a=a.href));
}
---
prints:
[snip ... http://www.morganstanley.com/;,
http://www.cs.columbia.edu/;, http://www.cse.tamu.edu;,
index.html, C++.html, bs_faq.html, bs_faq2.html,
C++11FAQ.html, papers.html, 4th.html, Tour.html,
programming.html, dne.html, bio.html, interviews.html,
applications.html, glossary.html, compilers.html]
Or perhaps better yet:
import arsd.dom;
import std.net.curl;
import std.stdio;
void main() {
auto document = new Document(cast(string)
get(http://www.stroustrup.com/C++.html;));
foreach(a; document.querySelectorAll(a[href]))
writeln(a.href);
}
Which puts each one on a separate line.
Re: For those ready to take the challenge
On Fri, 09 Jan 2015 13:50:28 +, eles wrote: https://codegolf.stackexchange.com/questions/44278/debunking- stroustrups-debunking-of-the-myth-c-is-for-large-complicated-pro Was excited to give it a try, then remembered...std.xml :(
Re: For those ready to take the challenge
On Fri, 09 Jan 2015 17:18:42 +, Adam D. Ruppe wrote: Huh, looking at the answers on the website, they're mostly using regular expressions. Weaksauce. And wrong - they don't find ALL the links, they find the absolute HTTP urls! Yes, I noticed that. `script src=http://app.js`/script` isn't a hyperlink. Wake up sheeple!
For those ready to take the challenge
https://codegolf.stackexchange.com/questions/44278/debunking-stroustrups-debunking-of-the-myth-c-is-for-large-complicated-pro
Re: [challenge] Lazy flatten/avoiding type forward reference with map
On 10/31/2013 10:19 PM, Ali Çehreli wrote:
...
Y Combinator? (No, I have not solved it yet. :) )
http://rosettacode.org/wiki/Y_combinator#D
Ali
Oh my god, my eyes!
auto y(S,T...)(S delegate(T) delegate(S delegate(T)) f){
struct F{ S delegate(T) delegate(F) f; alias f this; }
return (x=x(x))(F(x=f((T v)=x(x)(v;
}
Re: [challenge] Lazy flatten/avoiding type forward reference with map
But can you think of a more simple/elegant workaround? Is a standard lazy struct range authorized?
Re: [challenge] Lazy flatten/avoiding type forward reference with map
On 11/1/13, David Nadlinger c...@klickverbot.at wrote: I just thought I'd be interested to see what the best solution we can find in terms of conciseness is. Note that I've already asked this in D.learn: http://forum.dlang.org/thread/mailman.43.1383090512.9546.digitalmars-d-le...@puremagic.com
[challenge] Lazy flatten/avoiding type forward reference with map
A while back, somebody raised the topic of implementing a lazy
range for traversing/flattening a tree structure on #d.
The obvious (in terms of Phobos primitives) solution would be
something along the lines of this:
---
struct Node(T) {
T val;
Node!T[] children;
}
auto flatten(T)(Node!T root) {
import std.algorithm, std.range;
return only(root.val).chain(map!flatten(root.children).joiner);
}
void main() {
alias N = Node!int;
auto a = N(1, [
N(2, [
N(3, [
N(4)
])
]),
N(5)
]);
import std.stdio;
writeln(a.flatten); // [1, 2, 3, 4, 5]
}
---
But of course, that piece of code does not compile with current
DMD, as the return type of flatten() can't refer to the function
itself (during name mangling).
Now, one way around this would be to add an array() call at the
end of the return statement, which hides the type of map!flatten,
but at the cost of many unnecessary memory allocations. A second
option would be to use inputRangeObject to convert the return
value to ForwardRange!T (well, that is if it actually worked, due
to an implementation bug it leads to a runtime crash).
But can you think of a more simple/elegant workaround?
(Note aside: Obviously, the fact that the code relies on
recursion might be an issue, and a simple opApply-based solution
with a worklist stack would likely perform better. Still, I think
it's a simple, yet interesting problem.)
David
Re: [challenge] Lazy flatten/avoiding type forward reference with map
On 10/31/2013 12:09 PM, David Nadlinger wrote:
A while back, somebody raised the topic of implementing a lazy range for
traversing/flattening a tree structure on #d.
The obvious (in terms of Phobos primitives) solution would be something
along the lines of this:
---
struct Node(T) {
T val;
Node!T[] children;
}
auto flatten(T)(Node!T root) {
import std.algorithm, std.range;
return only(root.val).chain(map!flatten(root.children).joiner);
}
void main() {
alias N = Node!int;
auto a = N(1, [
N(2, [
N(3, [
N(4)
])
]),
N(5)
]);
import std.stdio;
writeln(a.flatten); // [1, 2, 3, 4, 5]
}
---
But of course, that piece of code does not compile with current DMD, as
the return type of flatten() can't refer to the function itself (during
name mangling).
Now, one way around this would be to add an array() call at the end of
the return statement, which hides the type of map!flatten, but at the
cost of many unnecessary memory allocations. A second option would be to
use inputRangeObject to convert the return value to ForwardRange!T
(well, that is if it actually worked, due to an implementation bug it
leads to a runtime crash).
But can you think of a more simple/elegant workaround?
(Note aside: Obviously, the fact that the code relies on recursion might
be an issue, and a simple opApply-based solution with a worklist stack
would likely perform better. Still, I think it's a simple, yet
interesting problem.)
David
Y Combinator? (No, I have not solved it yet. :) )
http://rosettacode.org/wiki/Y_combinator#D
Ali
Re: [challenge] Lazy flatten/avoiding type forward reference with map
On 10/31/2013 02:19 PM, Ali Çehreli wrote: Y Combinator? (No, I have not solved it yet. :) ) http://rosettacode.org/wiki/Y_combinator#D Ok, I was actually trying to find the following one: https://github.com/gecko0307/atrium/blob/master/dlib/functional/combinators.d Ali
Re: AI Challenge - Ants
dmd: glue.c:719: virtual void FuncDeclaration::toObjFile(int): Assertion `!vthis-csym' failed. Not able to reduce the code that causes it as it compiles fine here and it takes 10 minutes to upload new code and let it compile/play. 2011/11/8 bearophile bearophileh...@lycos.com maarten van damme: But I have also lost interest because of a couple of shortcommings, the hell it is to debug that thing and when it finally compiles fine on 2 machines it gives a cryptic error about glue.c (that had something to do with rdmd) What is the message of this cryptic error, and are you able to reduce the code that causes it? Bye, bearophile
Re: AI Challenge - Ants
Am 09.11.2011, 18:52 Uhr, schrieb maarten van damme maartenvd1...@gmail.com: dmd: glue.c:719: virtual void FuncDeclaration::toObjFile(int): Assertion `!vthis-csym' failed. Not able to reduce the code that causes it as it compiles fine here and it takes 10 minutes to upload new code and let it compile/play. 2011/11/8 bearophile bearophileh...@lycos.com maarten van damme: But I have also lost interest because of a couple of shortcommings, the hell it is to debug that thing and when it finally compiles fine on 2 machines it gives a cryptic error about glue.c (that had something to do with rdmd) What is the message of this cryptic error, and are you able to reduce the code that causes it? Bye, bearophile Try compiling all *.d source files at once with DMD 2.054 (x86_64) and -O -inline -release -noboundscheck, instead of using rdmd. That is basically what the server does. You may have triggered an unresolved and strange compiler bug unless this wouldn't happen with 2.056.
Re: AI Challenge - Ants
Looks like issue #6395 or any of the issues linked in there: http://d.puremagic.com/issues/show_bug.cgi?id=6395 It could actually depend on the order the source files are found and appended to the command line by the server's compile script. :-/
