Talk:Topological sort: Difference between revisions
m
→J implementation: fix <lang J> tags (now <syntaxhighlight lang=J>)
No edit summary |
m (→J implementation: fix <lang J> tags (now <syntaxhighlight lang=J>)) |
||
| (24 intermediate revisions by 10 users not shown) | |||
Line 5:
These are brief notes, and do not attempt to document the language itself.
<
parsed=. <@;:;._2 y
names=. {.&>parsed
Line 12:
assert.-.1 e. (<0 1)|:depends
(-.&names ~.;parsed),names /: +/"1 depends
)</
<code>parsed</code> is a list of lines. Each line is a boxed list of words. Each word is a boxed list of characters.
<code>names</code> is the first word extracted from each line.
Line 34:
└──────────────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴──────┴────────────┴────────┘
(Note: this is meant to be viewed in a fixed width font, and the non-alphabetic decorating characters are meant to be line drawing characters. If you are not seeing this, and you want to, you might try using a different browser. Or, if the text is fixed width but the line drawing characters are mis-aligned, you might try using a different fixed width font in your browser.)
:(There are other problems with using the box characters too, such as the extra space between lines. If it's just illustrative, try a mediawiki table instead. –[[User:Dkf|Donal Fellows]] 22:45, 1 March 2010 (UTC))
The result of <code>names e.S:1 parsed</code> is then:
Line 94 ⟶ 95:
Here's that alternate implementation. The algorithm remains unchanged -- I have just represented the dependencies using a different data structure.
<
parsed=. <@;:;._2 y
names=. {.&>parsed
Line 101 ⟶ 102:
assert.-.1 e. (i.@# e.S:0"0 ])depends
(-.&names ~.;parsed),names /: #@> depends
)</
In other words, instead of using a connection matrix, we use lists of name indices. In other words, the result of <code>names i.L:1 parsed</code> is
Line 124 ⟶ 125:
If I have been too brief on some subject, please feel free to ask questions. (I could, hypothetically, expand this discussion out into a tutorial on the J language, but I have already done something like that on a few rosetta code pages and that sort of thing gets tiring after a while -- especially when I do not get any feedback from the audience about their interests. Also I do not want to be spending too much time boring people who do not care at all about J.)
[[User:Rdm|Rdm]] 15:48, 2 September 2009 (UTC)
: [http://paddy3118.blogspot.com/2009/09/j-for-py-guy.html J for a Py Guy] --[[User:Paddy3118|Paddy3118]] 17:37, 2 September 2009 (UTC)
Note: Roger Hui has pointed out that, in the version of J I am using (version 6.02a), the expression <code>;@:{L:0 1~</code> is slow on large data sets (for example: trees with 2e5 nodes). For now, a faster (but more obscure) implementation of the same algorithm is <code>3 : '(*c) #^:_1 (I.c) <@;/. (;y){y [ c=. #&> y'</code>. In both cases, we are finding the grandchildren which correspond to the current children. [[User:Rdm|Rdm]] 18:21, 2 September 2009 (UTC)
== Clojure example ==
I don't know much about Clojure, but I did notice that most of its section's leader description describes the role of code in the example. Could someone migrate that description appropriately into comments within the code sample? --[[User:Short Circuit|Michael Mol]] 18:02, 25 March 2010 (UTC)
== Task Name? ==
As far as I see, all the Sorting tasks with the exception of the Topological Sort and Topological sort/Extracted top item start with "Sort ...". or "Sorting algorithm". Would it not be better for consistency to rename these two.--[[User:Dgamey|Dgamey]] 11:35, 10 August 2011 (UTC)
"Sort topologically"? Yeuch! I would hate to put the word topologically in a title. Maybe "Sort/Topological sort"? --[[User:Paddy3118|Paddy3118]] 12:27, 10 August 2011 (UTC)
: [[Sort/Topological]]? --[[User:Short Circuit|Michael Mol]] 14:08, 10 August 2011 (UTC)
: All of the "Sorting algorithms", like [[Sorting algorithms/Insertion sort]], can sort a list of numbers. "Topological sort" cannot sort a list of numbers, therefore it belongs not with the "Sorting algorithms", and retains its page name "Topological sort". --[[User:Kernigh|Kernigh]] 15:20, 10 August 2011 (UTC)
:: You can sort numbers using topological sort. A trivial example of course would be to sort them based on a "less than" or "greater than" relationship. However, you can use other relationships, such as "is a factor of" or "is a product of" or "is a hailstone predecessor of" or whatever else... That said, this task is not just about sorting, but also about putting things into buckets. And that, I think, is a good reason for keeping this task separate from the other [[Sorting algorithms]] tasks. --[[User:Rdm|Rdm]] 15:32, 10 August 2011 (UTC)
::Also this doesn't seem to have an algorithm. It's more like a class of sorts (like [[wp:comparison sort|comparison sorts]]). The class of items that it can sort shouldn't matter for including it under [[Sorting algorithms]], but the fact that it's not an algorithm should. --[[User:Mwn3d|Mwn3d]] 15:25, 10 August 2011 (UTC)
:I guess we could re-name all the 'Sorting algorithms/*' to 'Sort/Magnitude/Algorithms/*' then this could slot in as 'Sort/Topological' (as we don't specify any algorithms). See [[wp:Sorting]]. (I used the word magnitude rather than their use of the word intensity). Then again, we could just leave the 'Sorting algorithms/*' as they are. --[[User:Paddy3118|Paddy3118]] 17:46, 10 August 2011 (UTC)
: All other sorts require full ordering, that is for any two elements a and b, the comparison a < b or a <= b is meaningful. Topological sort has only partial ordering: if a depends on c and b depends on d, and there are no other dependencies, a < b or a < d doesn't have to be defined: dbca, dcba, cadb, etc are all valid result. It's really quite different. --[[User:Ledrug|Ledrug]] 18:55, 10 August 2011 (UTC)
::+1 on leaving as-is. --[[User:Paddy3118|Paddy3118]] 06:48, 11 August 2011 (UTC)
:: What about leaving it here, making sure some of the good notes above (i.e it's about more than just sorting) are in the task description as background (excuse me if they already are), and giving a redirect? Or perhaps just wait till the new SMW code is in and we can find it through sorting if we like. --[[User:Dgamey|Dgamey]] 03:02, 30 August 2011 (UTC)
== External link and Captcha problem ==
I am trying to add a Forth entry to the Topological sort page. Even if I just add the header for the Forth section to the Erlang section, the system tells me that I have added a new external link and I have to solve a captcha.
I first tried without JavaScript: After solving the picture puzzle, the captcha tells me to copy something to an empty box, but there is no empty box, only a filled box; and I also don't see a way to tell the system that I am done.
Then I tried with JavaScript enabled: I have to click on a box and it gives me the green check mark (in one case I had to solve a picture puzzle first), but the page is not saved yet. When I press "Save Page" again, I get another message about a new link and again a captcha.
I am not sure that this is the right place for such user-interface issues, but I did not find anything that looked more appropriate, and the problem about reporting new links that are not there seems to be specific to this page (it has not occured on other pages I edited).
: I have added a stub Forth entry to the page for you to fill in. (Thanks) --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 21:44, 22 February 2016 (UTC)
Thanks, I have now added the content to the entry.
| |||