AltME groups: search

Sorting seems to be the big bottleneck:


arraycount with sorted data (using maximum-of, same results as sorted):
>> time [arraycount copy SDat] 50
== 0:00:00.172956
fast-tally with unsorted data:
>> time [fast-tally copy Data] 50
== 0:00:00.357852
fast-tally with the sort step removed, with pre-sorted data:
>> time [fast-tally copy SDat] 50 
== 0:00:00.103735

For safe stable, sorting return -1, 0, +1 rather than true or false:
   http://www.rebol.com/docs/changes-2-5.html#section-72

example" 


sorting a list of first and last names first on last then on first 
in case of same last names

The basic compare function then (assuming you are sorting a block 
of objects) is:

   func [a b] [if a/surname = b/surname [return a/firstname < b/firstname] 
   return a/surname < b/surname]]

refining sunanda's example, sorting on selected fields

sort/compare s func [a b] [
	repeat n [2 4] [
		if a/:n < b/:n [return -1] if a/:n > b/:n [return +1]
	] 
	return 0
]


I just indented it to make it a bit easier to break up

I've used 'case statements for multiple levels of sorting, like that

getting a 5 second delay
 Got it. Hard to believe, but:

	write file form sort unique dict

is about a hundred times slower than:

	write file form dict


Sorting isn't so bad, but unique absolutely grinds it to a halt. 
Timings are:

parse		00:00.2
plus sort	00:00.8
plus unique	00:05

you have to worry about encodings when you do conversions. i don't 
see where the R2 server is doing any of that. Also, with UTF-8 there 
is no need to worry about encodings on searches and things like that. 
The only issue could be sorting, but that is also region specific 
so it's a completely different issue that R3 cannot solve globally 
either.

Of course FOREACH of map! would operate in the order that TO-BLOCK 
map! would return the keys and values at that moment. In the long 
run you would have to consider the order of FOREACH map! to be non-deterministic 
between calls. The map! type has no inherent ordering, so position 
and sorting are meaningless for it.

The sorting order should handle priorities, and the difference between 
word, /word, "word" and word! usage should be enough.

Adrian, what Brian is proposing will get you most of what you want, 
but what you are asking for seems to be a bit to specific and from 
my perspective doesn't add enough value to be worth the time to implement. 
 With intuitive sorting you'ld get all of the functions that require 
both an Integer! and a String! first followed by those that require 
an Integer! or a String!.  About 80% of the reason that I actually 
use Help is to see the order in which a function expects it's arguments 
to be in.  Searching for [Integer! String!] will list the functions 
that opperate on a string and require an index to that string at 
the top of the list and I think that's what you're really looking 
for.  Some people think in oppisite directions and want to declare 
the index first and others want to declare the string first.  It's 
just a matter of preference and doesn't change what the function 
does.

While I have your attention and I'm thinking about sorting I just 
thought I'd mention that I'm using the following work-around for 
the lack of /compare in sort:

; R3 /compare bug work around
sort-compare: func [
	blk
][
	; disorder the rows
	forskip blk 2 [change/part blk reduce [blk/2 blk/1] 2]
	; sort em
	sort/skip/reverse blk 2
	; reorder the rows
	forskip blk 2 [change/part blk reduce [blk/2 blk/1] 2]
	blk
]

so sorting an incomplete /skip would add nones into the block?

I would prefer GUI version. We should also create priority list - 
what should happen after the plugins are released? Release first 
host code, examples? Then what? Move onto parse? Unicode? (still 
things like collation, sorting not supported)? GUI?

Ladislav, I've tested random some more. The equal sign, =, is used 
to test in the end of RANDOM, if the result should be changed to 
0.0. This will change more values, than if =? was used. I use =? 
in my test. My test goes like this:

REBOL [
	Title:		"Random distribution test"
	Author:		"John Niclasen"
]

random/seed now
dist: clear []	; distribution
tt62: to integer! 2 ** 62
a: tt62 - 1024
loops: 100000
loop loops [
	i: random 1024
	if i > 512 [i: i + a]	; test close to 0.0 and close to 1.0
	y: i - 1 / tt62 * 1.0
	if y =? 1.0 [y: 0.0]	; the result of random 1.0
	y: form y
	either find dist y [
		dist/:y: dist/:y + 1
	][
		repend dist [y 1]
	]
]
while [not tail? dist] [
	dist/1: load dist/1		; change strings back to decimals
	dist: skip dist 2
]
dist: head dist
sort/skip dist 2	; sorting distribution
print dist
mean: 0.0
foreach [value count] dist [
	mean: value * count + mean
]
mean: mean / loops	; calculating the mean value
print mean	; this should be 0.5


The test is testing values close to 0.0 and close to 1.0. Notice 
the high count of 0.0 result compared to other low values. Also notice, 
how the mean value is close to 0.25, where it should be 0.5. Try 
out-comment the change of y to 0.0. Then the result will be much 
better.

Max - what you are proposing - could it serve to support collation 
mechanism? Because what we still lack is to support specific collation 
sorting - unless it is implemented, I refuse to claim, that R3 supports 
Unicode ...

I'm only concerned with latency with 100 clients... my current system 
uses SQL and bogs down nastily while I do analysis on 4000 items 
and their properties (sorting, filtering, finding etc)
I/O Costs:

L1: 3 cycles
L2: 14 cycles
RAM: 250 cycles
DISK: 41,000,000 cyles
NETWORK: 240,000,000 cycles

ah, so you think that the sorting won't work?

The point would be, were tables done correctly in RebGUI, that the 
pretty print formatting would come at cell rendering time rather 
than as input to the table. In the work I've been doing, Cyphre changed 
table for me so that it would allow sorting on strings that contain 
numbers.

I am in the "make a formatting function" camp, but it doesn't matter 
for math or numeric sorting.

Sort nicely worked for me, when sorting IP addresses. I switched 
from string type to tupple type upon BrianH's suggestion :-) It was 
initially "easier" for me to keep IPs as strings, but I was just 
lazy to use native REBOL dtype :-)

I'll try sorting ..

uses the Y coord. Use whatever sorting scheme you like.

any one know of a faster method than sorting a block to get the largest 
value inside of it?

in my tests... this:
     forall blk [ val: max val first blk]

is ~ five times SLOWER than this:
     last sort blk

actually, you are not sorting or traversing a long serie.
>>reduce [a]
== [[1 1 1 2 2 2 ...]]

your serie contains only one value.

i suggest to do a COPY A instead

Ah, less topological sorting than I thought.

graphic engines redraw everything at each redraw, even in 3D.   this 
is because of transparency and depth sorting.

New R3 GUI which fixes a few styles, like text list, although text 
list will eventually be rewritten:

http://94.145.78.91/files/r3/gui/r3-gui.r3


Style browser now shows style options, alphabetic sorting of style 
names, face debug option (currently broken in the R3 GUI):

http://94.145.78.91/files/r3/gui/style-browser.r3

another optimisation is that when you create a document you will 
obviously do alot of insert action so the idea is to regroupe the 
insert actions betwin  insert space
For example:


insert "a", insert "b"', insert "c"; insert " " -> trigger of the 
sorting algorithm insert "abc" [line1-:-0] (this optimisation can be 
seen in OpenOffice 3.2)
 

Would be better if instead of registery the action done by the user 
you register the mirror action to be apply to reverse it
then you have

delete "a", delete "b", delete "c"; delete " " -> trigger concatenation 
algorythm delete "abc"@line1:0, delete "space"@line1:3 (position 
here is set as line number followed by the caracters to pass in the 
line before reaching the character can speed up rendering if you 
are able to use remove index stuff in my opinion)

how powerfull is a table style? I expect it not being full grid capable, 
as Cyphre did in the past, however what's the basic functionality 
to expect?


- column sorting - two state, or three state? (I don't like when 
I can't get back the original sorting = unsorted), but that's just 
my point-of-view, and not importan feature initially
- column filtering like in MS Excel
- how much data the table handles?

column sorting: three state.
column filtering: yes.

how much data: lots of. In normal mode you're limited by memory, 
in DB mode you're limited by your DB system.

horizontal scrolling: not yet, but can be easily implemented (you 
can already select which columns to display).

Oh, sorting the todo list. No, the license isn't at the top.

- I / RMA will be the main communication channel. I have access to 
Rebol-3 twitter and there exists a RMA twitter.

- We will continue to work on the R3-GUI and release it as we did 
before (sometimes there might be longer periods of no-release, if 
we are doing massive changes)

- The main focus will be: fixing bugs, defining and writing down 
how datatypes are handled WRT conversion, priority, sorting etc.

I would add following "negatives" (depends upon how you look into 
it):


- no /libary extension and easy wrapping of DLLs. There was a bounty 
started to bring in kind of R2 DLL capabilities using extensions, 
Max was working on something, but did not deliver. Some ppl claim, 
that working with extensions is easy enough, much more powerfull, 
and that in fact R2 /library interface was weak in comparison in 
capabilities.


- weak and underpowered CALL.No /output or /wait parameter IIRC. 
Carl said, that R2 C code to it was complex, and that the code is 
eventually awailable for volunteer to bring in to R3. The outcome 
is - CALL is limited in usage in comparison to what can be easily 
achieved in R2.


- protocols. The only protocol IIRC was available was HTTP, done 
by Gabriele. It was HTTP 1.1 compatible, but due to some bug (?) 
it was downgraded to 1.0 version. No proxy support. Other protocols 
were done by some other ppl, I do remember Graham doing some work 
here. In regards to protocols, IIRC there was some work done by Kaj, 
who brought Curl networking extension to R3.


- under Windows console is a bit more inconvenient in usage than 
in R2, we use native Windows console, yet we don't have full console 
support, so we can't replace the native R3 one by e.g. Console2 or 
some other version ...


- DBAccess - forget R2 protocols available. The rescue is ODBC extension 
for R3


- CGI - no native CGI support in R3, though it should not be difficult 
to emulate


- Sorting & Unicode - althought we have Unicode strings available, 
sort is not adapted to that, and the question is, if it can be easily 
done ...

Sorting & Unicode - althought we have Unicode strings available, 
sort is not adapted to that, and the question is, if it can be easily 
done ...

 - this is not a disadvantage of R3, in this case R3 surely is better 
 than R2

Cheaper than sorting it during each find.

Merge sort is for when comparisons are *really* slow, sorting disk 
records slow. You have to have a really heavyweight mezz compare 
function to justify that. The overhead of the second series would 
be pretty high in cases where the speed difference would really matter. 
One of the inplace sorts would be better, as long as it's stable.

Read the ticket. "Stable" means a different thing when applied to 
sorting algorithms.

I ran into the problem when I was sorting words in a block and the 
bindings mattered.

Thus, you can sort certain permutations (the ones already sorted) 
much faster, than is the "information theoretical limit", but at 
the cost of exceeding it noticeably sorting other permutations.

Is there sort function (comparator) for no sorting, so this will 
be TRUE ?

block = sort/compare copy block :comparator

Sorting pairs. hmm...

>> sort [1x2 2x1]
== [2x1 1x2]

Doesn't make sense.

It definitely makes sense to me to expose SORT's basic grouping or 
sorting mechanism, so you can build your own sorter around its logic. 
I'm not sure I care about what datatypes come first or which order 
the "meaningless values" come in, just as long as it's consistent 
with SORT.

You can just use SORT to access SORT's sorting mechanism, no?

They definitely have *use* in SORT

- as far as I am concerned, I find it "meaningful" to implement a 
feature of the language that is "useful" (but that may be just me)

But there are much more important issues:


* the users shall be able to use their own sorting functions applying 
useful comparison operators (SORT has known issues)

* the users shall be able to utilize the advantages of having the 
data sorted, which, again, is possible if the compatible comparison 
functions are available

Max, although I think you're comparing O(1) vs O(n) parsing algorithms 
(random access vs linear)

(The indexing part is probably meant to be O(n.log n) because it 
involves sorting data, but should be taken apart from the parsing 
cost)

just wandering around, uhuh

steeve, I think I was using SWAP for some sort of sorting using the 
/part refinement.

But doing a sorting algorithm without any clue about memory alocations; 
is just ... clueless ;-)

It will be slower in average especialy for looping intensive computations 
like the sorting algorithms. I don't think the Red compiler can remain 
simple and beat a full featured optimizing c compiler.