Explain to a non-developer

[nokowi]

The most inefficient sorting (comparing everything to everything) takes 1/2(N^2+N) operations for N items

http://watson.latech.edu/book/algori...sSorting1.html

In a list of 100 items, that would be 5,050 operations for a complete sorting.

Mainstream computers in 2017 reached 1,000,000,000,000 operations per second. Your old computer might be 1000 times slower.

old computer: 0.000005 seconds
new computer: 0.000000005 seconds

Yes, sorting should be trivial, and there has to be some not-well-thought-out design to make sorting difficult.

Things are even worse when you consider things like the TR cache, which shouldn't require a resorting of a list but rather a removal of only one item.

I'm sure there are good reasons why DDO is slow, but those reasons seem to be centered around not thinking far enough ahead to what they want their design to do in the future, or simply not considering the end user. Vendor items and inventory interactions should not even cause noticeable delays. They don't in other games.

The list size would need to be on the order of 100,000 items to cause a noticeable sort delay. Bringing up images, or communication with the server are probably the larger issues -- and these should also be trivial with good design and a small number of images on the screen at any one time.

[simo0208]

It seems the big misunderstanding with above posts is the cost of database interactions versus small in memory operations (such as small sorts or pointer updates!)

The original question asked was how hard is sorting (small lists). The answer is is that it is not.

Some of the actions around sorting might have hugely expensive costs - especially if there is a network or dB involved, and one that can get congested or locked. But that was not the original question. TR cache is a pain , but I believe most inventory pains are actually intentional to get us to buy more inventory space. My toon with full tabs is just that much easier to play. Makes me want to buy more tabs on alts.

Once you *have* the data in memory , sorting a small list should be fairly trivial.

Agree 100% there. My point is just that the issue is far from trivial to get to the end user. But te act itself is not a huge challenge.

[bracelet]

Sorting isn't trivial.

Yes it is trivial. Reworking database fetches to bring everything into a std::vector without introducing a duping opportunity might be a bit tougher, but sorting is indeed trivial. It’s nonsense to say otherwise.

[minionofgruumsh]

How hard is it to sort a list? What is the difficulty of sorting the vendor lists so they have a sensible order?

I think the answer to your question lies in your qualifier of "a sensible order". What constitutes a "sensible order"? How are current lists *not* "sensible"? The fact that they exist in a consistently particular order every time you bring them up would imply that there is *some* order applied to them that *would* "make sense" if you knew the "behind the scenes" workings that go on to produce it.

So the difficulty in sorting a list in a "sensible order" is directly proportional to the difficulty of getting everyone to agree on what a "sensible order" is.

[EllisDee37]

Sorting isn't trivial. Using a prebuild language sort routine where the complexity has been optimized for you is easy. The process is easy, but depending on the sort algorithm and the number of items you need to sort it can be quite time consuming.

There aren't any large lists in DDO in terms of a single character looking at inventory, or a single vendor offering items, or even the cannith crafting shard machines. Not in terms of sorting, at least, where anything under 1000 is trivially small.

As for not using prebuilt library sorting routines, rolling your own is also trivially easy. Years ago I got interested in sorting algorithms and put together a sample program visually demonstrating the differences between 18 different sorting algorithms. As can be seen in that linked thread, most sorting algorithms are only a couple dozen lines of code.

For my Lite tools, I typically stick with quicksort, insertionsort and combsort. The only reason I use combsort is because it's particularly "clean" to drop a UDT array into the source code instead of sorting a simple array, which is much easier since I can just pass a "pointer" to the array, which I can't easily do with UDT arrays.

[Niminae]

How hard is it to sort a list? What is the difficulty of sorting the vendor lists so they have a sensible order?

Please sort the quests in the grouping panel so that it ignores a leading 'The.'

Or list them there as 'Quest_Name, The.'

[Niminae]

What are you talking about ? Sorting is one of the most basic ideas in any language, database, or comp Sci class.

Unless we're talking aasembly or, I don't know, bash ? The only real questing is HOW you want things sorted. Sorting is trivial. Assuming you know what you are sorting by.

Sorting in bash, or via SED or AWK, is also trivial. In bash you use *gasp* 'sort' plus command line arguments.

[Niminae]

Still an assumption.

How a database is pulled into an engine is a potential problem. A lot of old moving parts in DDO. Legacy code issues and all that. But hey, neither if us have seen the code I’m sure to know what the issue is. One thing is certain, if it were as easy in this game as you say, why wouldn’t they have done it already? They must just hate organization and their player base right?

I'm not sure if that was a deadpan snark or not. Text just doesn't convey that well at all. Remember all of the really embarrassing (or at least they should have been seen as such) typos and grammatical errors that used to exist all over the place? There were dozens and dozens of them. For years they were asked to fix them, and told repeatedly how unprofessional and sophomoric allowing these typos and grammatical errors to stand made them look. And all of that feedback, from multiple people, across literally years of time, was completely ignored. Cordovan said in one livestream that fixing them was viewed as embarrassing by the dev staff, because then the typo/grammer correction would need to be posted in the release notes, and so there was a reluctance to make those corrections even though that mindset and or culture was completely arse backwards.

And then one summer they hired an intern, and suddenly this wet behind the ears young adult makes all these other supposed adult professionals who presumably take pride in their work look like either a pile of 5th grade kids or a bunch of adult slackers by fixing all of the typos and grammar errors. If it was hard to make these corrections then they put their intern on the hard tasks, which doesn't make any sense. But you're saying that easy stuff should be done already unless they just hate organization and their player base, right? So, draw your own conclusions, because that's the history in a nutshell.

[Gremmlynn]

I'm not sure if that was a deadpan snark or not. Text just doesn't convey that well at all. Remember all of the really embarrassing (or at least they should have been seen as such) typos and grammatical errors that used to exist all over the place? There were dozens and dozens of them. For years they were asked to fix them, and told repeatedly how unprofessional and sophomoric allowing these typos and grammatical errors to stand made them look. And all of that feedback, from multiple people, across literally years of time, was completely ignored. Cordovan said in one livestream that fixing them was viewed as embarrassing by the dev staff, because then the typo/grammer correction would need to be posted in the release notes, and so there was a reluctance to make those corrections even though that mindset and or culture was completely arse backwards.

And then one summer they hired an intern, and suddenly this wet behind the ears young adult makes all these other supposed adult professionals who presumably take pride in their work look like either a pile of 5th grade kids or a bunch of adult slackers by fixing all of the typos and grammar errors. If it was hard to make these corrections then they put their intern on the hard tasks, which doesn't make any sense. But you're saying that easy stuff should be done already unless they just hate organization and their player base, right? So, draw your own conclusions, because that's the history in a nutshell.

To me it just sounds like they put the lowly (or possibly un-) paid intern on some scut work they didn't feel was worth paying others more to do. Kind of like not hiring a lawyer to clean your pool due to what you have to pay a lawyer an hour to do anything. My guess is that they simply pay programmers more than what they feel correcting typos is worth.

[boredGamer]

I'm not sure if that was a deadpan snark or not. Text just doesn't convey that well at all. Remember all of the really embarrassing (or at least they should have been seen as such) typos and grammatical errors that used to exist all over the place? .

Exactly.

To me it just sounds like they put the lowly (or possibly un-) paid intern on some scut work they didn't feel was worth paying others more to do. Kind of like not hiring a lawyer to clean your pool due to what you have to pay a lawyer an hour to do anything. My guess is that they simply pay programmers more than what they feel correcting typos is worth.

This is a terrible analogy. The lawyer has no professional pride in the cleanness of the pool. It's more like formatting errors in a legal document, with the lawyers name on it. *technically* he's paid on results, professional pride should drive him to clean up the **** in his environment. He should do it WITHOUT being told to do it.

Sorting in bash, or via SED or AWK, is also trivial. In bash you use *gasp* 'sort' plus command line arguments.

Absolutely right, I love nerd technicalities. I fear, however, we have gone the other way in the "sort" discussion from above where everyone was trying to make it the most complicated sort problem possible (somehow multiple languages, hardwares, rolling own sorts, infinite dynamic lists of unknown data) - and we have boiled it down to "sort anything on any parameter".

For fun - assembly sort (note - stolen, referenced, and I didn't really read it or verify it)

https://www.quora.com/What-is-the-co...rt-in-assembly

selection_sort_i64:
	; /*
    ; Input:
	; RDI = long long * array
	; RSI = length
	;
	; Pseudo-C code: 
    ;
	; for (int i = 0; i < n - 1; ++i) {
	;	 min = i
	;    for (int j = i + 1; j < n; ++j) {
	;		if a[j] < a[min]; min = j
	;	swap(i, min)
	;*/
 
	I64_SIZE equ 8
	LG_I64_SIZE equ 3
 
	cmp rsi, 1
	jle .end 			; Just end it if length <= 1
	xchg rsi, rdi		; rsi => left pointer
	mov rcx, rdi		; rcx => length
 
	; RDX will be the boundary for i: RSI + (N-1)*sizeof(int64)
	lea rdx, [rsi + rcx * LL_SIZE - LL_SIZE]
 
	; /*
	; Let's explain what's happening here.
	; RSI will be &a[i], RDX will be it's right boundary
	; RDI will be &a[j] (&a[i + 1]) and will loop n-i times
    ; RCX will be n-i and will be the counter for the inner loop
    ; RAX will track our minimum in the remaining of the array
	; RBX will 
	; */
.outer_loop:
	cmp rsi, rdx
	jge .end			; while (i < n - 1) {
	mov rax, [rsi]		;	min = a[i]
	mov rbx, rsi	    ;   min_i = i	
	push rax
 
	mov rdi, rsi
	add rdi, I64_SIZE	;	j = i + 1 // rdi => right pointer
	dec rcx				;	// rcx = n - i, inner loop counter
	push rcx
.inner_loop:
		cmp rax, [rdi]				; if (min > a[j])
		jle .min_less_or_equal
		mov rbx, rdi				;	min_i = j
		mov rax, [rdi]				;	min = a[j]
.min_less_or_equal:
		add rdi, I64_SIZE			; j += 1
		loop .inner_loop
	pop rcx				; // restore inner loop counter
	pop rax				; // restore a[i]
 
	cmp rsi, rbx		; // swap if minimum found
	jz .no_min			;	if (i != min_i) 
	mov rdi, [rbx]		;		temp = a[min]
	mov [rbx], rax		;		a[min] = a[i]
	mov [rsi], rdi		;		a[i] = temp
.no_min:
	add rsi, I64_SIZE	;	i += 1
	jmp .outer_loop		;	} // end outer loop
.end:
	ret

[Gremmlynn]

This is a terrible analogy. The lawyer has no professional pride in the cleanness of the pool. It's more like formatting errors in a legal document, with the lawyers name on it. *technically* he's paid on results, professional pride should drive him to clean up the **** in his environment. He should do it WITHOUT being told to do it.

When "on the clock" my experience has always been to do what the boss asks or expects, not what one feels they should be doing. Spending one's time cleaning up messes when one is expected to be making new saleable product is a good way to no longer have a profession to have pride in.

Also, the point of the analogy seems to have flown over your head. The point was, one doesn't pay a lawyers wages to have their pool cleaned. For that matter, no successful law firm has a lawyer doing what a paralegal could be (though they very well might charge as if they had), the lawyers are doing something else they can bill some other client for that actually requires their expertise. Though I'm sure they look over whatever has their name on it.

[boredGamer]

When "on the clock" my experience has always been to do what the boss asks or expects, not what one feels they should be doing. Spending one's time cleaning up messes when one is expected to be making new saleable product is a good way to no longer have a profession to have pride in.

Also, the point of the analogy seems to have flown over your head. The point was, one doesn't pay a lawyers wages to have their pool cleaned. For that matter, no successful law firm has a lawyer doing what a paralegal could be (though they very well might charge as if they had), the lawyers are doing something else they can bill some other client for that actually requires their expertise. Though I'm sure they look over whatever has their name on it.

Clearly the point didn't "fly over my head" as I obviously understood it, disagreed with it, explained why, and offered a more apt analogy.

Perhaps ?luckily? I'm in a job where some level of autonomy is not only encouraged, but absolutely expected. No one is paid to only do the most valuable thing they do, and similarly, to do the best job at the most valuable thing you do requires you to do things other people could do (like fix typos).

I mostly like how you ended your bizarre response agreeing a lawyer will "look over" what has their name on it (after you literally made the point the paralegal would do so, and the lawyer would be fired for doing so themselves).

Whatever, totally off-topic.

[Seikojin]

How hard is it to sort a list? What is the difficulty of sorting the vendor lists so they have a sensible order?

Well, when it comes down to it, at this state of the game, neigh impossible.

There are many subjects on sorting lists in code. And the reason there are many, is because it gets complicated quickly.
https://www.bing.com/search?q=sort+l...6d7891b0756455


In DDO, it really comes down to time versus deadlines. When DDO was in early development, the pace of getting code churned out to a testable build was such that developers would find the easiest way to do a sort on a list, have it break, try a different method, have it kind of work, but break when merged to the daily build, and repeat that try a new method to have it fail over and over again until the sprint/deadline is looming, so they find one that works, is kind of hacky, and limited. However it is not perfect, scalable, or very reusable. Fast forward 5 years and they start appending that list to sort and it doesn't sort properly since it was written in a hacky way.

And this isn't a DDO problem. I mean it happens here, however it is a problem in just about every application and game in existence. Deadlines talk, good code walks.

To improve this, they would have to refactor the code. And it would take soo many hours to do right, that no manager would approve of it on any paid work timetable. I would guess that just a single sell/buy vendor, to get their sort in order, could take a year of development time alone. No release testing. To get it unit test passable, without build verification testing automation exploding, or the build exploding.

[Scrapco]

To improve this, they would have to refactor the code. And it would take soo many hours to do right, that no manager would approve of it on any paid work timetable. I would guess that just a single sell/buy vendor, to get their sort in order, could take a year of development time alone. No release testing. To get it unit test passable, without build verification testing automation exploding, or the build exploding.

I feel dumber just reading this. The "unit test" part makes me think you're joking, along with a year of time to put in one line of code, but I know you're not.

Well, when it comes down to it, at this state of the game, neigh impossible.

Basic sorting?

Hey Lynnkerbell, can you spend 20 minutes some afternoon this week and sort the vendor lists on some random attribute just to mess with people? That'd be amusing.

[cpw_acc]

I'm going to take an educated guess here and say that the problem isn't just sorting on its own, but sorting a list over a distributed environment where the items to display are not necessarily all fetched at once.

E.g.

If you display a list at the client side, but only want to fetch the first 20 items, then when the user scrolls or clicks a button you want to fetch the next 20 and so on. This would be because if you fetched all the hundreds of items at once it would create an obvious and unacceptable delay to the user, so you 'spread' the delay by retrieving in batches.

I'll also guess that maybe a character's data isn't stored, by default, in a very clear database structure, but maybe as some kind of compressed data in a single 'object field' or something. So retrieving the items in whatever fixed-order they were stored in would likely be trivial.

But allowing the user to select an (almost) arbitrary sort order would require first fetching and unravelling all the items and then holding then into some temporary storage area so you can sort them, just so the batches could be returned in the right order. Again, introducing a possibly unacceptable delay.

I'm not saying this problem is insurmountable - its just my guess as to why sorting may not be 'trivial'!

[EllisDee37]

I'm going to take an educated guess here and say that the problem isn't just sorting on its own, but sorting a list over a distributed environment where the items to display are not necessarily all fetched at once.

That's known as online processing, and is a well-understood aspect of sorting. There are online algorithms, most notably insertion sort, that handle online sorting just fine.



Just to throw this out there: We're talking about in-game lists that are currently, already sorted, so clearly sorting the list isn't some complex hardship many in the thread are imagining. The OP is asking for a different sort order.

[Seikojin]

I feel dumber just reading this. The "unit test" part makes me think you're joking, along with a year of time to put in one line of code, but I know you're not.

Basic sorting?

Hey Lynnkerbell, can you spend 20 minutes some afternoon this week and sort the vendor lists on some random attribute just to mess with people? That'd be amusing.

It is like it was already said before, new item categories really threw a wrench in the existing sorting. And that was well after a ton of other item categories were added.

I am suggesting devs have already tried changing the default sort and how sort order work, a long time ago, and that it caused more problems come build time.

And you are right, I am saying it is that big of a lift for a single line of code. Integration is every developers nightmare. I have been doing this for almost 20 years now, and I can say without a doubt, that a single line of code in an existing product is never something that goes right on in without regressions.