Re: String Comparison Operator
On Sunday, 30 April 2017 at 19:05:18 UTC, bauss wrote: On Sunday, 30 April 2017 at 16:15:41 UTC, Xinok wrote: On Sunday, 30 April 2017 at 15:31:39 UTC, Jolly James wrote: Is there a String Comparison Operator in D? Yeah, just the usual comparison operators: "abc" == "abc" "abc" != "ABC" ~ is for string concatenation, i.e.: "abc" ~ "def" == "abcdef" Just to clarify. It's not actually a string concatenation operator, it's an array appending operator. Strings are just an alias for immutable(char)[] and not actually a type unlike other languages like C#, Java etc. where strings are objects. In fact it doesn't have any operators that doesn't work with any other type of arrays. Just like functions such as replace etc. aren't necessarily string functions, but works with any type of arrays. Regarding concatenation vs appending, it's kind of both depending on the type of the operands. What I mean is all of the following are valid: [10, 20] ~ [30, 40] == [10, 20, 30, 40] // Concatenation [10, 20] ~ 30 == [10, 20, 30] // Appending 10 ~ [20, 30] == [10, 20, 30] // Prepending
Re: String Comparison Operator
On Sunday, 30 April 2017 at 15:31:39 UTC, Jolly James wrote: Is there a String Comparison Operator in D? Yeah, just the usual comparison operators: "abc" == "abc" "abc" != "ABC" ~ is for string concatenation, i.e.: "abc" ~ "def" == "abcdef"
Re: Why double not? (!!)
On Saturday, 19 November 2016 at 03:52:02 UTC, Ryan wrote: Why do I see double `not` operators sometimes in D code? An example it the last post of this thread. http://forum.dlang.org/thread/ktlpnikvdwgbvfaam...@forum.dlang.org import core.sys.windows.windows : GetConsoleCP; bool hasConsole = !!GetConsoleCP(); Thanks. It's a more concise way of writing: GetConsoleCP() != 0 You can do this in C/C++ as well (and presumably some other languages).
Re: @nogc inconsistent for array comparison depending on mutability of elements
On Friday, 8 April 2016 at 10:15:10 UTC, Dicebot wrote: On Friday, 8 April 2016 at 09:56:41 UTC, Nick Treleaven wrote: Semantically, array literals are always allocated on the heap. In this case, the optimizer can obviously place the array on the stack or even make it static/global. So @nogc is enforced by the optimizer? Yes, sadly. What? O_o I stated that it's not and explained why doing so would be a bad idea. To make it sane one would need to make a list of all optimization DMD makes in that regard and put them into spec as mandatory for all compilers.
Re: @nogc inconsistent for array comparison depending on mutability of elements
On Friday, 8 April 2016 at 01:36:18 UTC, rcorre wrote:
@nogc unittest {
int[2] a = [1, 2];
assert(a == [1, 2]); // OK
immutable(int)[2] b = [1, 2];
assert(b == [1, 2]); // fail: array literal may cause
allocation
}
Is there any logic behind allowing the comparison with `a` but
not `b`, or is this a compiler bug?
Semantically, array literals are always allocated on the heap. In
this case, the optimizer can obviously place the array on the
stack or even make it static/global. However, it would be in poor
design to rely on the optimizer to satisfy @nogc. It comes down
to portability; if the code compiles successfully with one
compiler, then it should compile successfully in any other
compiler.
Also, the way that compilers are typically built is that semantic
analysis is done in the frontend and optimization is done in the
backend. Trying to build a bridge between these two would be
incredibly difficult and make implementing the compiler much more
complex with little gain.
Re: How to sort a range
On Wednesday, 9 March 2016 at 15:39:55 UTC, rcorre wrote: Still curious as to why it fails; maybe the range is getting copied at some point? I guess I need to step through it. That's my suspicion as well. It seems that OnlyResult is pass-by-value so every time it gets passed to another function, it creates a copy of all the elements. A simple solution is to provide a wrapper type which refers to the elements in the original container. However, I'm going to argue that the sort function is fine but the modifications you made to OnlyResult are incorrect. I tried running your example of only(...).sort but got a compilation error. Similarly, trying to sort a static array also gives a compilation error. However, if I slice the static array before passing it to sort (thus passing by reference), then it works just fine.
Re: How to force evaluation of range?
On Friday, 12 February 2016 at 20:43:24 UTC, Taylor Hillegeist
wrote:
So I have this code and I have to add the element
.each!(a => a.each!("a"));
to the end in order for it to evaluate the range completely and
act like I expect it too. Is there a better thing to put in
the place of
.each!(a => a.each!("a"));?
...
The following combination might work:
.joiner.each;
http://dlang.org/phobos/std_algorithm_iteration.html#.joiner
http://dlang.org/phobos/std_algorithm_iteration.html#.each
Re: How to force evaluation of range?
On Saturday, 13 February 2016 at 01:11:53 UTC, Nicholas Wilson wrote: ... If you just want the range evaluated use walkLength It might work in this case, but in general this won't work for any range which defines .length as a member. In that case, walkLength will simply return .length of that range.
Re: How to force evaluation of range?
On Saturday, 13 February 2016 at 03:16:09 UTC, cym13 wrote:
On Saturday, 13 February 2016 at 02:17:17 UTC, Xinok wrote:
On Friday, 12 February 2016 at 20:43:24 UTC, Taylor Hillegeist
wrote:
So I have this code and I have to add the element
.each!(a => a.each!("a"));
to the end in order for it to evaluate the range completely
and act like I expect it too. Is there a better thing to put
in the place of
.each!(a => a.each!("a"));?
...
The following combination might work:
.joiner.each;
http://dlang.org/phobos/std_algorithm_iteration.html#.joiner
http://dlang.org/phobos/std_algorithm_iteration.html#.each
Why not just .each; ?
The thing he's trying to iterate over is a range of ranges. A
single .each will only iterate over the outermost range so you
need .joiner first to "flatten" the range, then you can use .each
on that result.
Re: Collapsing n-dimensional array to linear (1 dimensional)
On Friday, 22 January 2016 at 12:07:11 UTC, abad wrote:
Let's say I have an array like this:
int[][][] array;
And I want to generate a linear int[] based on its data. Is
there a standard library method for achieving this, or must I
iterate over the array manually?
What I'm thinking of is something like this:
int[] onedim = std.array.collapse(array);
You can use std.algorithm.joiner but you have to call it twice to
flatten a 3D array to a 1D array.
import std.algorithm, std.stdio, std.array;
void main()
{
int[][][] arr = [[[1], [2, 3]], [[4, 5], [6, 7]], [[8],
[9, 10], [11]]];
int[] arr2 = arr.joiner.joiner.array;
writeln(arr);
writeln(arr2);
}
http://dlang.org/phobos/std_algorithm_iteration.html#.joiner
Re: Balanced match with std.regex
On Tuesday, 15 December 2015 at 01:29:39 UTC, Jakob Ovrum wrote: Thanks, that makes sense. String manipulation in D without regex is pretty nice anyway, so it's not a big loss. There is a library named Pegged which can match against balanced parens: https://github.com/PhilippeSigaud/Pegged
Re: D programming video tutorial
On Sunday, 13 December 2015 at 20:29:47 UTC, Pederator wrote: Hi. Does anybody who is familair with D consider to make a comprehensive D programming video tutorial / training / course? This could be encouraging and helpful for people to start with D. It could also help in promoting D programming language. This is a question for all the community, please comment what do you think about this idea, we will know if there is an interest in such a training video, or is it just me. It's almost two years old now but I found this series of videos on D: https://www.youtube.com/playlist?list=PL-zvF7DyWePQad_E6Y9J9kbYvM7AjnBD1
Re: functional way doing array stuff/ lambda functions
On Saturday, 12 December 2015 at 23:36:43 UTC, cym13 wrote:
...
So, in your example:
int product(const ref int[] arr) {
import std.array: array;
import std.algorithm: reduce;
arr = arr.reduce!((p, i) => p*i).array;
}
A good post overall but you got reduce wrong. In D, reduce
computes and returns the result immediately, not a lazy range.
The following code is correct:
int product(const ref int[] arr) {
import std.array: array;
import std.algorithm: reduce;
return arr.reduce!((p, i) => p*i)();
}
Example: http://dpaste.dzfl.pl/fc2c2eab2d02
Re: Purity of std.conv.to!string
On Saturday, 26 September 2015 at 17:08:00 UTC, Nordlöw wrote: Why is the following code not pure: float x = 3.14; import std.conv : to; auto y = x.to!string; ??? Is there a reason for it not being pure? If not, this is a serious problem as this is such a fundamental function. I don't know the exact reason but I found a couple of functions which could be marked pure which are not, including strippedOctalLiteral and isOctalLiteralString. It's possible that some function was simply overlooked and needs to be marked pure or infer purity. The larger issue at hand is that the compiler doesn't tell you where an impurity lies, merely that it exists. I mentioned this issue not too long ago while experiencing my own difficulties respecting purity.
Re: foreach multiple loop sugar
On Tuesday, 18 August 2015 at 15:51:55 UTC, ixid wrote:
Though sugar seems to be somewhat looked down upon I thought
I'd suggest this- having seen the cartesianProduct function
from std.algorithm in another thread I thought it would be an
excellent piece of sugar in the language. It's not an earth
shattering change but it makes something very common more
elegant and reduces indentation significantly for multiple
nested loops. Braces make nested loops very messy and any
significant quantity of code in the loop body benefits from not
being in a messy nesting.
...
What's wrong with just putting all the foreach statements on a
single line?
foreach(i; 0..10) foreach(j; 0..10) foreach(k; 0..10)
{
writeln(i, j, k);
}
Re: Does D have syntax for adding subscopes to classes?
On Wednesday, 12 August 2015 at 15:47:37 UTC, Adam D. Ruppe wrote: Example with them: ... That's the idea I had except I would use a struct instead because using a class requires a second allocation.
Is Key Type?
is there a trait in D or Phobos which will tell you if a type can be used as a key for an associative array? For example, where T is some type: static assert(isKeyType!T) int[T] hashTable = ...
Re: Map Purity
On Sunday, 28 June 2015 at 15:55:51 UTC, jmh530 wrote:
My understanding of pure is that a function labeled pure can
only include pure functions. I've been confused by the fact
that a function calling map (like below) can be labeled pure
without any problems. The only way I can rationalize it is that
map really isn't a function, it's (if I'm understanding it
correctly) a template that creates a template function that
calls a struct template.
auto test_map(T)(T x) pure
{
return x.map!(a = a + a);
}
This is related to
http://forum.dlang.org/thread/ppmokalxdgtszzllz...@forum.dlang.org?page=1
but maybe my question is more basic.
Map isn't explicitly marked as pure. D can infer purity for
templated functions, so as long as you give it a pure predicate,
map can be inferred as pure. This only works for templated
functions; non-templated functions must be explicitly marked as
pure.
Re: Associative array on the heap
On Tuesday, 19 May 2015 at 00:31:50 UTC, Freddy wrote:
Sorry mis-phrased my question,
Who do you allocate a pointer to an associative
array(int[string]*).
Ignoring the why for a moment, one trick is to place it in an
array literal so it's heap allocated. This requires writing an
associative array literal with a single key-element pair though.
int[string]* a = [[zero:0]].ptr;
Another trick is to initially define the associative array in a
class. Since classes are heap allocated, you can allocate an
instance of the class and grab a pointer to the associative array.
class HeapAA
{
int[string] a;
}
int[string]*b = (new HeapAA).a;
Purity not enforced for default arguments?
The following code fails to compile because unpredictableSeed is
impure:
void main()
{
foreach(i; 0..10) writeln(pureRandom);
}
pure uint pureRandom()
{
auto r = Random(unpredictableSeed);
return r.front;
}
However, make unpredictableSeed a default argument, wrap the call
in another pure function, and it compiles:
void main()
{
foreach(i; 0..10) writeln(pureRandom2);
}
pure uint pureRandom2()
{
return pureRandom;
}
pure uint pureRandom(uint seed = unpredictableSeed)
{
auto r = Random(seed);
return r.front;
}
I'm inclined to believe this is a bug. While pureRandom could be
considered weakly pure, pureRandom2 has no arguments so it should
be strongly pure. Yet, it yields a different value on every call.
Re: Purity not enforced for default arguments?
On Tuesday, 10 March 2015 at 22:00:29 UTC, safety0ff wrote: On Tuesday, 10 March 2015 at 21:56:39 UTC, Xinok wrote: I'm inclined to believe this is a bug. https://issues.dlang.org/show_bug.cgi?id=11048 Thanks for the link, and I didn't mean to post this in D.learn. .
Re: Sorted Array Wrapper Range
On Wednesday, 3 December 2014 at 21:02:05 UTC, Nordlöw wrote: Have anybody written a generic automatically sorted range wrapper for RandomAccessRanges? I guess http://dlang.org/library/std/range/assumeSorted.html should play a key role. I see two typical variants: - Direct: Always sorts on write() and modify() - Lazy: Sorts lazily on read() read() of course uses binarySearch There was a relevant discussion about a month ago here: http://forum.dlang.org/thread/uhfpppdslxdghycon...@forum.dlang.org Otherwise, there's RedBlackTree, but I'm not aware of anything that works over any random-access range.
Re: How to initialise array of ubytes?
On Saturday, 29 November 2014 at 20:47:09 UTC, Paul wrote:
On Saturday, 29 November 2014 at 20:22:40 UTC, bearophile wrote:
This works:
enum MAPSIZE = 3;
void main() {
ubyte[MAPSIZE][MAPSIZE] map2 = 1;
}
This doesn't work:
enum MAPSIZE = 3;
ubyte[MAPSIZE][MAPSIZE] map1 = ubyte(1);
void main() {}
Why isn't this working?
I'm afraid I don't know. I would guess it's something to do
with trying to initialise the array in the global scope but
you've also changed the expression in the non-working example.
I don't have access to my machine at present so I can't
experiment!
More generally, it's because one is static (as in global /
thread-local) and the other is not. Take the working example, put
static in front of the declaration, and you'll get the same
error.
There are different rules regarding the initialization of static
and non-static variables. My guess, they're implemented as
separate features in the compiler, so when vector operations were
introduced, nobody thought to implement this feature as a way to
initialize static arrays as well.
Why the DMD Backend?
Given that we have GDC with the GCC backend and LDC with the LLVM backend, what are the benefits of keeping the DMD compiler backend? It seems to me that GCC and LLVM are far more developed and better supported by their respective communities. They have superior optimizers and are better equipped for migrating D to new platforms. On the other hand, from what I gather, there's lots of work to be done on DMD on improving support for x64 Windows and ARM. It's a genuine question, which is why I posted this to D.learn. I don't follow development on the backend and overall I'm unfamiliar with compilers, so I'm not sure what the benefits are of the D community continuing to maintain it's own backend.
Re: More flexible sorted ranges?
On Sunday, 2 November 2014 at 17:21:04 UTC, Ola Fosheim Grøstad wrote: On Sunday, 2 November 2014 at 16:59:30 UTC, bearophile wrote: Ola Fosheim Grøstad: Shouldn't sorted range maintain the invariant automatically in order to remain typesafe? Yes, of course. If SortedRange is fixed, please also switch the names of upperBound and lowerBound… They are currently wrong. An upperBound on something should return the values lower than it and a lowerBound should return values larger… (C++ got it right). D got it right. C++ returns an iterator which can be a bit confusing. D returns a slice so it's meaning is much clearer. https://en.wikipedia.org/wiki/Upper_and_lower_bounds http://www.cplusplus.com/reference/algorithm/upper_bound/
Re: More flexible sorted ranges?
On Sunday, 2 November 2014 at 15:13:37 UTC, bearophile wrote:
I have often arrays that are sorted, and sometimes I'd like to
append items to them. So I'd like to write something like:
SortedRange!(Foo[], q{ a.x b.x }) data;
data ~= Foo(5);
immutable n = data.upperBound(Foo(2)).length;
This means having an array of Foos as sorted range, and
appending an item to it keeping the sorting invariant (so in
non-release mode the append verifies the array is empty or the
last two items satisfy the sorting invariant), and this allows
me to call functions like upperBound any time I want on 'data'
without using any unsafe and unclean assumeSorted.
Is this possible and a good idea to do?
Bye,
bearophile
My concern is that SortedRange only accepts a range which is
random-access and limits its functionality to those primitives.
Concatenation is not required for random-access ranges, so should
we expect SortedRange to overload this operator?
Re: More flexible sorted ranges?
On Sunday, 2 November 2014 at 20:06:51 UTC, Ola Fosheim Grøstad wrote: On Sunday, 2 November 2014 at 19:54:38 UTC, Xinok wrote: D got it right. C++ returns an iterator which can be a bit confusing. D returns a slice so it's meaning is much clearer. No, according to docs D has defined the lower bound to be the negation of the lower bound… Sorry, you're right, it's not an upper bound. I read that definition a few times over and still got it wrong. O_o In terms of what to call it, perhaps what you're looking for is upper set? https://en.wikipedia.org/wiki/Upper_set
Re: More flexible sorted ranges?
On Sunday, 2 November 2014 at 20:19:12 UTC, bearophile wrote: Xinok: My concern is that SortedRange only accepts a range which is random-access and limits its functionality to those primitives. Concatenation is not required for random-access ranges, so should we expect SortedRange to overload this operator? I understand, that's why I am asking this here... I think the desire to keep a sorted range around and grow it keeping its invariant is a common enough need for my code. Currently I keep an array then I use assumeSorted + upperBound, but this is not safe nor nice. Perhaps sorted ranges should become more transparent in Phobos. There are other invariants beside sortness that can be useful to carry around, like set-ness (every item is unique inside this collection) and few more. Bye, bearophile I take back my original argument. As of 2.066, the requirements for SortedRange have been relaxed so it now accepts input ranges. The documentation needs to be updated to reflect this change. Still, I'm not comfortable to adding concatenation to SortedRange. I would prefer named functions which append / prepend elements with the guarantee that it preserves the invariant. In general, I don't feel that SortedRange is an ideal solution anyways. Wrapping ranges in a struct adds too much overhead and we can't extend the functionality of it. Would it be possible to replace SortedRange with a @sorted attribute or something?
Trouble reproducing compilation error
I'm currently receiving several errors when trying to compile this code with DMD 2.066 (beginning with RC1): https://github.com/Xinok/XSort The compiler throws an error because it's unable to deduce a type for the predicate in a few places. This repository compiles just fine in DMD 2.065 and earlier (more specifically, 2.066 beta 5 and earlier). I'm very certain that this is a bug given that I never experienced this issue before. However, I'm finding it impossible to reproduce the bug so I can file a bug report. I'm not sure what exactly is causing it or if there's something specific in the context of this code that's triggering it. The only thing that I can deduce is that, in each case, an instance variable is being compared to an array element, e.g.: int[] arr = [10, 20, 30]; int value = arr[0]; pred(value, arr[1]); // Instance variable compared to array element This one is stumping me and I could use some help in tracking down this bug.
Re: Trouble reproducing compilation error
This is the full compiler output: combsort.d(90): Error: template D main.pred cannot deduce function from argument types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(81): Error: template instance combsort.combSortLinear!(pred, uint[]) error instantiating combsort.d(135): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) combsort.d(151): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(82): Error: template instance combsort.combSortGallop!(pred, uint[]) error instantiating forwardsort.d(218): Error: template D main.pred cannot deduce function from argu ment types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) forwardsort.d(138): Error: template D main.pred cannot deduce function from argu ment types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) forwardsort.d(52): Error: template D main.pred cannot deduce function from argum ent types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(84): Error: template instance forwardsort.forwardSort!(pred, uint[]) error instantiating heapsort.d(119): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) heapsort.d(102): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(99): Error: template instance heapsort.heapSort!(pred, false, uint[] ) error instantiating heapsort.d(119): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) heapsort.d(102): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(101): Error: template instance heapsort.heapSort!(pred, true, uint[] ) error instantiating heapsort.d(221): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(103): Error: template instance heapsort.bottomUpHeapSort!(pred, fals e, uint[]) error instantiating heapsort.d(221): Error: template D main.pred cannot deduce function from argumen t types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(104): Error: template instance heapsort.bottomUpHeapSort!(pred, true , uint[]) error instantiating insertionsort.d(45): Error: template D main.pred cannot deduce function from arg ument types !()(uint, uint), candidates are: benchsort.d(37):benchsort.main.pred(T)(T a, T b) benchsort.d(108): Error: template instance insertionsort.insertionSort!(pred, ui nt[]) error instantiating
Re: Optimize my code =)
On Friday, 14 February 2014 at 16:56:29 UTC, bearophile wrote: Craig Dillabaugh: this.data = new T[this.dim.size]; with: this.data.length = this.dim.size It's the same thing. Bye, bearophile Not quite. Setting length will copy over the existing contents of the array. Using new simply sets every element to .init. Granted, this.data is empty meaning there's nothing to copy over, so there's a negligible overhead which may be optimized out by the compiler anyways. There's also the uninitializedArray function: http://dlang.org/phobos/std_array.html#.uninitializedArray
Re: My first D module - Critiques welcome.
On Monday, 23 December 2013 at 21:34:34 UTC, John Carter wrote:
So I resolved to learn D, and try code as idiomatically as I
could.
So here is a trivial module that encodes and decodes roman
numerals.
https://bitbucket.org/JohnCarter/roman/src/9ec5b36b9973426f35b0ab9dfd595cb3b305e39e/roman.d?at=default
I also attempted to do it in Best Practice Test Driven
Development form
with commits on every change.
So you can see the blow by blow history of how it grew.
I would welcome any critique, advice, flames, recommendations,
etc. etc.
Thanks for your help and patience with various stupid newbie
questions I
asked in the process!
Overall, I say it's not bad. I just have a few comments on your
coding style.
Be consistent with your opening braces. Personally, I always
place it on the next line, regardless if it's a function or
something else.
unittest
{
}
instead of:
unittest {
}
The standard in Phobos is that 1 tab = 4 spaces. Otherwise, when
using spaces to align code, make sure it's consistent and
everything lines up. (lines 145-155)
There are a series of unittests which could be merged together.
Keep the line comments to keep different tests separate, but
there's no need to have multiple unittests which contain nothing
more than a few simple asserts. Or as bearophile suggested, use
an in-out table. Besides for grouping things together and making
your code more organized, it's better for those of us who use
IDEs, so we can collapse the unittest with a single click.
Re: Quadratic time to sort in a simple case?
On Friday, 19 April 2013 at 22:37:45 UTC, Ivan Kazmenko wrote: So, why isn't TimSort the default? I would actually argue for this, not for safety (introsort is an adequate solution) but for different reasons. Timsort is stable and it's faster on data with low entropy, being nearly instantaneous on already sorted lists. I would guess it's the better choice for most cases. Then for those cases where stable sorting isn't necessary and unstable sorting would be faster, the user could choose the second option.
Re: Quadratic time to sort in a simple case?
On Tuesday, 23 April 2013 at 14:12:01 UTC, bearophile wrote: Andrei Alexandrescu: There's not the C++ STL sort. Any implementation is fine as long as it has O(n log n) expected run time. This seems to use the Introsort: http://www.sgi.com/tech/stl/sort.html I don't know if Xinok has tested a 2-pivot quicksort (called by the usual Introsort setting). Bye, bearophile On an average case, two-pivot quick sort will increase the number of comparisons by about 50%, reason being that about half the elements will be greater than the first pivot and have to he compared to the second pivot. There's also a greater complexity given there are three partitions rather than two, increasing the amount of I/O necessary. Introsort is simply a quick sort which falls back to a heap sort after so many recursions to guarantee O(n log n) performance. I've implemented this using a median of five and it works excellent. This is what I plan to contribute to Phobos. Choosing a random pivot will always invoke average performance where as finding the median of N elements usually achieves better performance on sorted lists. You also have to be careful that equal elements are distributed equally among both partitions, else a list with many elements equal to the pivot will still achieve poor performance. (equal elements would all fall onto one side of the pivot)
Re: Quadratic time to sort in a simple case?
On Friday, 19 April 2013 at 21:03:23 UTC, Ivan Kazmenko wrote: Hi! Consider a sorted array. Append an element that is less than all the previous elements. Then sort the array again by the sort function from std.algorithm. With n = 30_000 as in the example, this takes time of the order of a second on a modern computer, which is clearly O(n^2). I am using DMD 2.062. I filed a bug report for this issue a year ago: http://d.puremagic.com/issues/show_bug.cgi?id=7767 I've been meaning to fix this issue myself. Time allowing, I'll do it soon.
Re: Quadratic time to sort in a simple case?
On Saturday, 20 April 2013 at 16:35:25 UTC, Dmitry Olshansky wrote: And this all is good but TimSort allocates O(N) memory. The constant in front of N is smallish less then 1.0 but it could cause some grief. Worst case is O(n/2), but it starts small and doubles in size as needed. On a partially sorted array, it may only use a small amount of memory.
Re: Quadratic time to sort in a simple case?
On Tuesday, 23 April 2013 at 01:28:56 UTC, bearophile wrote: Xinok: I've been meaning to fix this issue myself. Time allowing, I'll do it soon. Good. And if you are willing, please also take a look at the parallel sort problem I've raised: http://forum.dlang.org/thread/iyunhhsbmurqyouyr...@forum.dlang.org Bye, bearophile I could, but I'm not sure what the general consensus is on std.parallel_algorithm as it's been brought up before in a similar context.
Re: do-while loops
On 12/28/2011 8:29 AM, bearophile wrote:
One thing that I often find not handy in the design of do-while loops: the scope of their
body ends before the while:
void main() {
do {
int x = 5;
} while (x != 5); // Error: undefined identifier x
}
I would just rewrite it like so:
void main(){
while(true){
int x = 5;
if(x != 5) continue;
break;
}
}
Re: Array initialization quiz
On 11/30/2011 7:50 AM, Steven Schveighoffer wrote:
On Tue, 29 Nov 2011 15:06:11 -0500, Jonathan M Davis
jmdavisp...@gmx.com wrote:
The type of the index should be irrelavent to the underlying loop
mechanism.
Note that the issue is really that foreach(T i, val; arr) {...}
translates to for(T i = 0; i arr.length; ++i) {auto val = arr[i]; ...}
Why can't it be (aside from the limitation in for-loop syntax, but you
get the idea): for(size_t _i = 0, T i = _i; _i arr.length; i = ++_i)
{auto val = arr[_i]; ...}
Same issue with foreach(i; -10..10), what if I wanted to do foreach
(ubyte i; ubyte.min..ubyte.max + 1). This should not result in an
infinite loop, I should be able to use foreach to iterate all the values
of ubyte. The compiler should just figure out how to do it right.
-Steve
This actually doesn't compile:
foreach (ubyte i; ubyte.min..ubyte.max + 1)
Error: cannot implicitly convert expression (256) of type int to ubyte
It's a little more to type, but just write a property which does an
explicit cast:
foreach(_i; ubyte.min .. ubyte.max + 1){
ubyte i(){ return cast(ubyte)_i; }
}
Re: Array initialization quiz
On 11/30/2011 11:46 AM, Steven Schveighoffer wrote:
On Wed, 30 Nov 2011 10:54:11 -0500, Xinok xi...@live.com wrote:
On 11/30/2011 7:50 AM, Steven Schveighoffer wrote:
On Tue, 29 Nov 2011 15:06:11 -0500, Jonathan M Davis
jmdavisp...@gmx.com wrote:
The type of the index should be irrelavent to the underlying loop
mechanism.
Note that the issue is really that foreach(T i, val; arr) {...}
translates to for(T i = 0; i arr.length; ++i) {auto val = arr[i]; ...}
Why can't it be (aside from the limitation in for-loop syntax, but you
get the idea): for(size_t _i = 0, T i = _i; _i arr.length; i = ++_i)
{auto val = arr[_i]; ...}
Same issue with foreach(i; -10..10), what if I wanted to do foreach
(ubyte i; ubyte.min..ubyte.max + 1). This should not result in an
infinite loop, I should be able to use foreach to iterate all the values
of ubyte. The compiler should just figure out how to do it right.
-Steve
This actually doesn't compile:
foreach (ubyte i; ubyte.min..ubyte.max + 1)
Error: cannot implicitly convert expression (256) of type int to ubyte
It's a little more to type, but just write a property which does an
explicit cast:
foreach(_i; ubyte.min .. ubyte.max + 1){
ubyte i(){ return cast(ubyte)_i; }
}
This is hugely inefficient...
foreach(_i; ubyte.min..ubyte.max + 1){
ubyte i = cast(ubyte)_i;
}
But my point was, foreach over a range gives me all the elements in a
range, regardless of how the underlying loop is constructed. The
limitation by the compiler is artificial.
I remember at one point there was someone who had actual code that
resulted in a loop for ubytes, or was trying to figure out how to
foreach over all possible ubyte values.
-Steve
It shouldn't be. The compiler should be smart enough to inline the
function and optimize the typecast to something like this:
void main(string[] args){
foreach(_i; ubyte.min .. ubyte.max + 1)
writeln(*cast(ubyte*)_i);
}
This would actually be faster since you don't have to iterate two variables.
Ranges help
This is in relation to my sorting algorithm. This is what I need to
accomplish with ranges in the most efficient way possible:
1. Merge sort - This involves copying elements to a temporary buffer,
which can simply be an array, then merging the two lists together. The
important thing is that it may merge left to right, or right to left,
which requires a bidirectional range.
c[] = a[0..$/2];
foreach(a; arr) if(!b.empty !c.empty) if(b.front = c.front){
a = b.front; b.popFront();
} else{
a = c.front; c.popFront();
}
2. Range swap - First, I need to do a binary search, which requires a
random access range. Then I need to swap two ranges of elements.
while(!a.empty !b.empty){
swap(a.front, b.front);
a.popFront(); b.popFront();
}
That's the best I can come up with. I'm wondering if there's a more
efficient way to accomplish what I have above.
I also need to figure out the template constraints. Would this be
correct? Or would this be too much?
isRandomAccessRange !isFiniteRange isBidirectionalRange hasSlicing
Pointers and Ranges
I'm new to ranges and while I understand the basic concept, I don't know everything about them. With arrays, you can simply use arr.ptr to infer a type automatically. So I was wondering, is there an equivalent for ranges? What I'm looking for is the ability to do *p as well as p[1] or p[-1] with ranges.
