sorting - Fast reverse sort in (SWI) Prolog -

-

i'm looking fast way sort list in reverse order in prolog. algorithmically should perform standard sort, options i've come slower, obvious reasons.

predicate rsort1/2 sorts , reverses.

rsort1(l1, l2) :-     sort(l1, tmp),     reverse(tmp, l2).

predicate rsort2/2 uses predsort/3 custom comparator.

rsort2(l1, l2) :-     predsort(reverse_compare, l1, l2).  reverse_compare(delta, e1, e2) :-     compare(delta, e2, e1).

to test performance i've generated huge random list this:

?- size = 1234567,    findall(n, (between(1, size, _), n random(size)), ns),    assert(test_list(ns)). size = 1234567, ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258|...].

these runtimes standard sort:

?- test_list(ns), time(sort(ns, nss)). % 2 inferences, 7.550 cpu in 8.534 seconds (88% cpu, 0 lips) ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...], nss = [0, 1, 3, 5, 8, 10, 12, 14, 16|...].

... rsort1:

?- test_list(ns), time(rsort1(ns, nss)). % 779,895 inferences, 8.310 cpu in 9.011 seconds (92% cpu, 93850 lips) ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...], nss = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].

... , rsort2:

?- test_list(ns), time(rsort2(ns, nss)). % 92,768,484 inferences, 67.990 cpu in 97.666 seconds (70% cpu, 1364443 lips) ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...], nss = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].

can better rsort1 , rsort2 speedwise?

if you're after sorting routine portable (i.e., defined using prolog), won't able implement faster (or fast, need reverse sort order) predicates execute sorting routines natively in c/c++, such sort/2 or msort/2.

if speed of overriding concern here, of course write own non-portable predicate external definition reverse sorting. example, swi-pl c++ interface used (see examples there) write c++ definition of rsort/2, perhaps using comparison predicates implemented in c++.

similarly, write rsort/2 in c using swi-pl c interface. src/pl-list.c in swi-prolog source contains implementations of sorting methods (namely nat_sort()) used sort/2, msort/2 , keysort/2. implement rsort/2, might need follow implementation , tweak/reverse interpretation of calls compare() describes standard order of terms.


Comments

Post a Comment

Popular posts from this blog

android - Spacing between the stars of a rating bar? -

-
ho can set spacing beween stars? thats ratingbar: ratingbar = (ratingbar) inflater.inflate(r.layout.ratingbar, null); ratingbar.setlayoutparams(new layoutparams(layoutparams.wrap_content, layoutparams.wrap_content)); the layout: <?xml version="1.0" encoding="utf-8"?> <ratingbar xmlns:android="http://schemas.android.com/apk/res/android" style="@style/mystyle" android:layout_alignparentright="true" android:layout_height="19dp" android:layout_width="wrap_content" android:numstars="5"> </ratingbar> the style: <style name="mystyle" parent="@android:style/widget.ratingbar"> <item name="android:progressdrawable">@drawable/android_r2_ratingstar_yellow</item> <item name="android:indeterminatedrawable">@drawable/android_r2_ratingstar_grey</item> </style> thanks, cheers you have ...
Read more

html - Instapaper-like algorithm -

-
does of algorithm extracts contents webpage? instapaper ? there 2 steps instapaper does: find main content block on page (excluding headers, footers, menus etc) from content block extract , format text to find content block (typically html block element, div containing key page text content) instapaper uses algorithm 1 used readability . can @ source of readability.js see what's going on, @ core tries find area on page highest text/link ratio, although has other simple scoring metrics (e.g. off top of head, things ratio of text commas, para elements etc) go heuristics. once have identified root node element, relevant content, you'll need format it, if want can pull node element containing text out of source document , insert yours, in reality you'll want remove existing styles , apply own, standard , feel. if want output nice text-only can use jericho's renderer . update1 : should mention else instapaper - follow 'pagination' links (...
Read more

c# - How to execute a particular part of code asynchronously in a class -

-
i creating speech recognition engine that's going respond user commands.i have created button enable , disable speech recognition per user convenience.i have used dispose() of speech engine disable speech recoginition.here code private void button1_click(object sender, routedeventargs e) { engineon = !engineon; if (engineon) { speechengine = speech.createspeechengine(); //speech class creates , returns new speech engine. speechengine.audiolevelupdated += new eventhandler<audiolevelupdatedeventargs>(speechengine_audiolevelupdated); // use system's default microphone speechengine.setinputtodefaultaudiodevice(); speechengine.loadgrammar(new dictationgrammar()); // start listening speechengine.recognizeasync(recognizemode.multiple); } else { speechclass.myengine.dispose(); } } but disposal of speech obj...
Read more