Talk:Bucket queue

GA Review

This review is transcluded from Talk:Bucket queue/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Colin M (talk · contribs) 00:13, 1 July 2021 (UTC)

Stay tuned for initial thoughts/feedback. :) Colin M (talk) 00:13, 1 July 2021 (UTC)

So for reference, I did take a data structures course or two as an undergrad, but that was about a decade ago, so I hope that puts me at around the expected level of sophistication of the readership of this article.

I'm only about halfway through, and need to rest my brain before working through the rest, but thought I would drop my comments so far in case you want to get a headstart:

• Brilliant infobox image. :)
  • Thanks, glad you liked it. I was worried some humorless reviewer was going to tell me to take it out. —David Eppstein (talk) 23:08, 5 July 2021 (UTC)
• O(C) in the infobox is not understandable without the context provided later in the body. Not sure the best way to handle this. An explanatory footnote? Or even some small text after the table in the infobox?
  • This is a general problem with infoboxes (see WP:DISINFOBOX): they can be very inflexible and unable to express the sort of nuance that is easy to express in article text. For this reason I am usually disinclined to use them at all, but in this case since we have an infobox specifically for priority queues I thought I probably couldn't get away with omitting it. Rather than trying to find a way to add an explanatory note in a way that readers could find, I changed O(C) to O(#priorities). —David Eppstein (talk) 22:56, 5 July 2021 (UTC)
• The article at Bucket (computing) is not very helpful in this context, since it basically says "bucket is a term that can is used in computer science with a variety of possible meanings". Maybe gloss it as referring to a container data structure, per the first body section?
  • Done by linking Bucket (computing) to an earlier instance of the word bucket and using the container link at this point instead. —David Eppstein (talk) 23:05, 5 July 2021 (UTC)
• I know it's a non-trivial ask, but I really think a small example would help a lot here. Basically like here's an example of a small queue. To insert a new element x, we do this, and here's what the resulting state looks like. To find the min we do this.
  • Example section added. —David Eppstein (talk) 16:19, 6 July 2021 (UTC)
• To remove an element x with priority p, remove x from the container at A[p]. I'm imagining that we could think of the elements in the queue as, say, tuples of identifiers and priorities, so that, for example, our priority 4 bucket could contain (Alice, 4), (Bob, 4), and (Carol, 4). In this view, a straightforward reading of the quoted sentence would seem to me to be saying that I can ask you to delete specifically Alice, or Bob, or Carol, and you can do it in constant time. But is that actually what you're trying to say? Or is it that you can remove some element with priority 4 in constant time? (I think this is the kind of confusion that a small worked example might help with.)
  • Rewritten to clarify that p can be determined from x rather than provided as an argument to the remove operation. —David Eppstein (talk) 00:19, 6 July 2021 (UTC)
    • I think this still leads to the same misapprehension. The fact that the line begins To remove an element x,... gives the impression that this is a recipe parameterized by x (similar to the previous bullet, which is parameterized by x). Perhaps it would be clearer if it started with To remove an element with priority p,...? Colin M (talk) 15:50, 6 July 2021 (UTC)
      • No, the element is the argument to the operation, not p. Why do you think this should not be parameterized by x? —David Eppstein (talk) 16:19, 6 July 2021 (UTC)
        • Ohhhh. For some reason I thought the article had presented this operation as constant time, so I inferred it couldn't possibly be parameterized by arbitrary x. But no, the article doesn't say that at all, I was just confused. Sorry, that's on me! Colin M (talk) 16:52, 6 July 2021 (UTC)
          • Wait, sorry, I was wrong about being wrong. The article does say insertions and removals take constant time. How can you delete an arbitrary element from a linked list or dynamic array in constant time? There are two citations after the sentence that contains that statement, but I'm not seeing how either of them verify this claim about constant time removals. Colin M (talk) 17:24, 8 July 2021 (UTC)
            • You have to know where the element is (that is, either its index in the dynamic array or the identity of the list element object representing it in the linked list), and for linked lists it needs to be doubly linked. Deleting an element from a doubly linked list is standard, taught in freshman-level computer science courses, and beyond the scope of the article, but in any case the answer to your question is: to delete doubly-linked list object x, set x.previous.next=x.next and x.next.previous=x.previous, with some additional cases depending on whether you're using a circular list or whatever else you're doing at the ends of a list. To delete an element from a dynamic array, move the last element of the array into its position and decrement the array length. How to find where the element is, in either case, is also standard, beyond the scope of the article, and can be handled by using an instance variable on the element, a dictionary mapping elements to their locations, or (if the elements have small index numbers assigned to them) an array mapping those instance numbers to locations. These pointers to element locations need to be updated whenever the location of an element changes, of course. Updating them takes constant time per location change. This is all no different than other priority queues: If you are using a binary heap for an algorithm like Dijkstra's that involves priority-changes, you need to have some way of tracking the location of each element in the heap. It is not mentioned in our binary heap article, not often mentioned in textbooks about using binary heap, and even omitted from some standard implementations of heaps (Python heapq comes to mind; you can't quickly change priorities because you can't quickly find elements) but it is the exact same issue. Similarly, this issue is glossed over in our sources for bucket heaps, but as it is a basic and much more widespread issue with algorithm implementation, I think it is off-topic here. If we had an article on the topic of how to track locations of objects in other data structures then we could at least link to it, but I think we don't. —David Eppstein (talk) 23:26, 8 July 2021 (UTC)
              • I looked again at what our sources on Dial's algorithm say about this issue. Older sources often expand subsidiary data structures into explicit representations, while modern treatments would encapsulate them more abstractly. A typical older approach is to give vertices index numbers and represent the doubly linked lists of vertices in buckets by having a single global next and previous array indexed by these numbers. Dial and Bertsekas are typical in this respect. Among other sources, here is textbook Edelkamp & Shroedl's entire coverage of this issue: "For DecreaseKey we generally assume that a pointer to the element to be deleted [sic] is available". Mehlhorn & Sanders, Varghese, and Festa don't cover this issue at all. I conclude that we don't have the available sourcing to say more than what we say in the article, that these operations can be performed in constant time but without detailed explanations of how. —David Eppstein (talk) 18:28, 9 July 2021 (UTC)
                • (Sorry for the delayed response - was away from wiki for a few days.) I'm still concerned about this claim. There are sort of two related angles, related to two different GA criteria:
                  1. Comprehensibility (GACR 1a). We proceed through the following statements: 1) Buckets are typically implemented as linked lists, or possibly dynamic arrays or dynamic sets. 2) To remove an item from a bucket queue, we locate the bucket that contains that item, and remove the item from that bucket. 3) "In this way [...] removals take constant time". I think to an average reader, this is likely to create confusion. Not only does 3 not follow from 1 and 2, it appears to contradict them, since deletion of an arbitrary element from a linked list or dynamic array is not generally understood as a constant time operation. (I think you disagree with me on this point, based on what you said about the implementation of efficient deletions being standard exercises in freshman-level courses. All I can tell you is that I have taken courses on data structures and theoretical CS at and beyond the freshman level, and this was still confusing to me. I also showed it to a friend who is actively involved in theoretical CS research, and they found it confusing.)
                  2. Verifiability (GACR 2). We are making a blanket statement that deleting an arbitrary element from a bucket queue is a constant-time operation. Is there a source that directly supports this claim? Note that I don't think this can be satisfied by citing a description of a particular algorithm using bucket queues which includes a particular mechanism for efficient deletion as part of a decrease-priority subroutine.

                  Since, as I mentioned, it seems we disagree on the comprehensibility issue, maybe we should focus on the verifiability side. If you can add a citation to support the claim that deletion from bucket queues is a constant-time operation, I'd be happy to consider this resolved. Colin M (talk) 17:38, 12 July 2021 (UTC)

                  The source that is most explicit about this, Edelkamp & Schroedl, does not actually include a delete operation in its operations. It instead has two bundled operations extract = findmin + delete (slower because of the findmin part) and changepriority = delete + insert, which they say takes constant time. I think it is clearer to keep them unbundled but at your insistance on pedantically following what the sources say instead of allowing obvious inferences from them I have similarly bundled the operations. Also the infobox apparently uses the bundled extract operation so I have changed its time bound to match. And yes, I do totally disagree with you about the time for deleting an element from a linked list or dynamic array. It is a constant time operation, if you are not so incompetent a programmer as to have lost track of what you are trying to delete. If you don't know what you are trying to delete, you can't do it at all. If you don't know how to write a program, you can't do it at all. That sort of nit-picking does not change the fact that these operations take constant time. It is getting into WP:CHEESE territory. —David Eppstein (talk) 19:34, 12 July 2021 (UTC)

                  Thanks. Given your stated disagreement, you may want to edit Template:List data structure comparison to correct the stated big-theta figures, or to clarify that they apply only to incompetents. Colin M (talk) 22:01, 12 July 2021 (UTC)

                  That template says the time for linked lists is constant, plus "search time", inapplicable in this case. It gives a time for dynamic arrays that applies to maintaining ordered lists, different from their use here as a container. (The difference is that if you want to maintain the list order you have to move many other array elements into the deleted position, but to use a dynamic array as a container, without maintaining the list in the same order, you only need to move a single element, the one that was previously at the end of the array.) You appear to be casting about for anything to support your disagreement, without adequately understanding what you are reading and what its domain of applicability is, rather than going by what the actual sources on this subject say. That is, committing original research yourself. Is that what a GA review should be? —David Eppstein (talk) 22:27, 12 July 2021 (UTC)

Your earlier comment simply said deleting an element from a linked list or dynamic array [...] is a constant time operation (if you are not incompetent). It seems you are now retreating to a weaker claim. Colin M (talk) 22:34, 12 July 2021 (UTC)

By the way, the introduction still makes the claim about constant-time removals. Colin M (talk) 22:41, 12 July 2021 (UTC)

Well, it's still a correct claim, but fixed for consistency with the rest of the article. —David Eppstein (talk) 22:50, 12 July 2021 (UTC)

• I think it's worth mentioning at least one concrete example of a sort of container data structure that might be used for buckets. Also, to be clear, there are constraints on what sorts of data structures we can use if we want to achieve the stated complexities for each operation, right? Is this so obvious it goes without saying? Actually, the citations that I've checked so far all say the buckets are linked lists - are there sources that say anything otherwise?
  • Done, adding two possibilities: linked lists (an old-fashioned way of doing things) and dynamic arrays (a more modern choice). —David Eppstein (talk) 23:05, 5 July 2021 (UTC)
    • I would still feel more comfortable if this were cited. At this point I've looked at a fair number of the sources cited in the article and can't recall any that talk about using any data structure other than a list. Colin M (talk) 16:58, 6 July 2021 (UTC)
      • That's because most of those sources are older, from a time when a linked list was the standard way to do this. I added a more modern source (Henzinger et al 2019) that talks about using both abstract container types and dynamic arrays here. —David Eppstein (talk) 19:01, 6 July 2021 (UTC)
• In this way the time to search for the minimum-priority element is reduced to the difference between the previous lower bound and its next value; I think this could be made clearer. Previous to what? Next following what?
  • Rewritten as part of handling the next point. —David Eppstein (talk) 00:14, 6 July 2021 (UTC)
• When searching for the minimum priority element, the search can start at L instead of at zero, and after the search L should be left equal to the priority that was found in the search. The citation for this doesn't exactly match the procedure you're describing. Rather they give a version where the tracked index is always precisely that of the first non-empty bucket.
  • Ok, it looks like Dial's version does use this sort of lazy searching (although it's not entirely clear because it's buried in source code that does not separate out the data structure operations from the algorithm that uses the operations), while Skiena's is more eager. It doesn't make a big difference to the structure — the same searches happen either way. I rewrote to describe both, with the lazy version cited to Dial. —David Eppstein (talk) 00:14, 6 July 2021 (UTC)
• The set cover problem has as its input a family of sets, with the desired output being a subfamily of as few sets as possible having the same union. The first time I read this I parsed it as "a subfamily of as few sets as possible having the same union [as each other]". Which, yeah, doesn't make sense, but I just couldn't produce a more sensible reading (until I read the set cover problem article). I think a few more words would help here (e.g. "having the same union as the original family.")
  • Done. —David Eppstein (talk) 00:17, 6 July 2021 (UTC)

Colin M (talk) 00:01, 2 July 2021 (UTC)

A few more comments:

• In many applications of monotone priority queues such as Dijkstra's algorithm, the minimum priorities form a monotonic sequence, so... This is sort of an odd wording. This is true of all applications of monotone priority queues, by definition, no?
  • Rewritten to put the monotone priority queue link later. —David Eppstein (talk) 00:20, 6 July 2021 (UTC)
• Could you briefly explain how Dial (1969) verifies the claim in "Optimizations" about the O(n+c) runtime? (I don't mean in the article itself, but just here.) I found a copy and looked it over casually but found it difficult to connect the content with the cited claim.
  • I replaced this with a newly-found textbook source (Bertsekas), which explains Dial's algorithm I think much more clearly than Dial's original paper, and also includes the time analysis. —David Eppstein (talk) 00:32, 6 July 2021 (UTC)
• This variant of Dijkstra's algorithm is also known as Dial's algorithm, after Robert B. Dial, who published it in 1969. Citation for it being known by this name?
  • Now sourced to Bertsekas. The difficult here was that searching Google Scholar or Google Books for "Dial's algorithm" finds hundreds of sources, most relevant but of low quality. But I think the Bertsekas source is a good one for this. —David Eppstein (talk) 00:32, 6 July 2021 (UTC)

Colin M (talk) 03:59, 4 July 2021 (UTC)

Comments

• To me, this looks acceptable as is; I only have minor comments.
  1. The opening sentence ("In the design and analysis of data structures, a bucket queue[1] (also called a bucket priority queue[2] or bounded-height priority queue[3]) is a priority queue for prioritizing elements whose priorities are small integers") doesn't make clear that we are talking about a data structure to readers who do not recognise the term "priority queue". If the reader has not picked this up, the mentioning of the analogy to pigeon-hole sort, an algorithm, might be confusing. It's also a little unambiguous in the lead whether the topic of the article is a specific data structure or a family of similar data structures, although perhaps that is not a bad thing: I like the way the 'Operation' section distinguishes between 'Basic data structure@ and 'Optimisations'.
     • Reordered lead to put the abstract data type first and the various alternative names much later. —David Eppstein (talk) 07:23, 6 July 2021 (UTC)
  2. We might mention initialisation time. Incidentally, Johnson 1981 doi:10.1007/BF01786986 is relevant here.
     • Ok, I added a paragraph about this to the end of the "Optimizations" section. —David Eppstein (talk) 07:15, 6 July 2021 (UTC)
  3. The set of applications given is very nice. — Charles Stewart (talk) 13:29, 2 July 2021 (UTC)

@Colin M and Chalst: Ok, I think I have addressed all comments. Please take another look. —David Eppstein (talk) 16:19, 6 July 2021 (UTC)

Round 2

Thanks for the updates, they all look great (modulo the one outstanding comment above about citation for bucket data structure choice). I'll start with some minor/nitpicky comments:

• This structure can handle the insertions and deletions of elements with integer priorities I think this would flow better if you removed the, or if you de-pluralized insertions and deletions. Also, since it's the start of the first section of the body, I'd prefer restating the name of the data structure over "this structure".
  • Done. —David Eppstein (talk) 19:20, 6 July 2021 (UTC)
• Another optimization (already given by Dial 1969) can be used to save space when the priorities are monotonic and, Should we specify minimum priorities here?
  • The same optimization works mutatis mutandis for max-prioritization. —David Eppstein (talk) 19:20, 6 July 2021 (UTC)
• over the course of the algorithm the number of these changes of priorities is just the sum of set sizes This could perhaps be made clearer. The sum of the sizes of which sets?
  • Rephrased: "sum of sizes of the input sets". —David Eppstein (talk) 20:21, 6 July 2021 (UTC)
    • Wouldn't it be more correct to say that the number of priority updates is at most the sum of the sizes of the input sets? Colin M (talk) 18:01, 8 July 2021 (UTC)
      • If you include the covering set among the ones whose priorities change, then it is actually exactly the sum of sizes of the input sets. Every set has its priority decremented once for every one of its elements. —David Eppstein (talk) 23:38, 8 July 2021 (UTC)
• In this way, the total time for the data structure to find these sets is proportional to the maximum initial priority, which is at most the number of elements to be covered. "total time... to find these sets" is a little ambiguous. Which sets? It's not immediately clear whether you're talking about the total runtime to find the set cover, or the time to find one set (i.e. the runtime of one iteration of a loop within the algorithm).
  • Moved the upper bound on priorities earlier, to the sentence about this being monotonic, and replaced this sentence with a more generic one saying the total time is linear. —David Eppstein (talk) 20:24, 6 July 2021 (UTC)

And here are some more substantial comments:

• An important piece of information that is commonly covered in RS on this subject is what considerations lead to this data structure being chosen over other priority queue implementations. I think this should be covered in the article, even if it's just a one-liner. (e.g. could just quote or paraphrase Skiena, which says it's "usually the right priority queue for any small, discrete range of keys".)
  • Ok, added something about this to the lead. And again, there is no good reason for quoting or close paraphrasing here; it is not difficult to express the same sentiment in different words. —David Eppstein (talk) 19:50, 6 July 2021 (UTC)
    • My intention was not to mandate any particular wording, but just to offer one possible suggestion. Colin M (talk) 22:19, 6 July 2021 (UTC)
• Their numbers of steps add in a telescoping series to at most C. According to the linked article, a telescoping series involves cancellation of positive and negative terms. I don't see where the negative terms come into play in this case. Are you sure this is an accurate description? Is there a source you could cite that describes it in these terms?
  • We're adding a sequence of differences between indexes, where each index in the sequence appears positively in one difference and negatively in the next. That is exactly what the term "telescoping series" describes. And your quest to find sources that describe each topic with exactly the same phrasing that we use in the article is lurching towards a hope that the article violates our restrictions against close paraphrasing. —David Eppstein (talk) 19:30, 6 July 2021 (UTC)
    • I don't think this is a very generous characterization of my position... To be clear, my intention with a comment like this is to start a conversation, not mandate any specific change. There's a reason a lot of these comments feature hedging language ("I don't see", "are you sure", question marks). To be more explicit, what I was trying to communicate with this comment was: I'm failing to understand how the term applies in this case. If you think I've identified a genuine error, please fix it. If you think the term does apply, could you try to explain how it applies or provide a citation, whichever is less effort? Colin M (talk) 22:34, 6 July 2021 (UTC)
      • The telescoping series part was intended only as a simple explanation of why the sum adds to C, but since you apparently found that confusing, I replaced it with a simpler explanation. —David Eppstein (talk) 05:48, 7 July 2021 (UTC)
        • Just to respond to the somewhat pointed edit summary on Special:Diff/1032398380: the problem is not that the concept of a telescoping sum is too technical. It's that you said the number of steps form a telescoping sum. Which would seem to imply that there are negative quantities of steps involved. But thank you, I think the new wording is clearer. Colin M (talk) 17:12, 8 July 2021 (UTC)
• a bucket queue can be used to obtain a time bound of O(n + m + dc), where n is the number of vertices, m is the number of edges, d is the diameter of the network, and c is the maximum (integer) link cost The source cited for this statement gives the runtime as "O(N + Diam*MaxLinkCost)", where I believe they're using N to mean just the number of nodes (in the later "Exercises" section they refer to "all N nodes").
  • Replaced the Varghese source (which appears to have made a small mistake in the statement of the time bound) with Bertsekas. Removed "n +" from the time bound, to match the new source (anyway it is redundant). —David Eppstein (talk) 19:54, 6 July 2021 (UTC)
• The same source (Varghese 2005 pp. 78-80) is used to cite the subsequent claim about the modular optimization, but I don't think it really serves as appropriate verification. AFAICT, this technique is only briefly alluded to in the last exercise, but it doesn't support the specific claims in the cited sentence (i.e. priorities span a range of width c+1, and space is reduced to O(n+c)).
• That source also says that "Dial's algorithm" refers specifically to the version with the modular optimization, which contradicts what we say in the article.
  • (For both previous bullets): You can't have it both ways: is this a source that describes the modular optimization, or not? And did you fail to notice that the part of this section about applying the modular optimization to shortest paths already had two sources? So the fact that one of the sources describes only the application of the optimization and not its analysis is non-problematic, as the analysis is still covered by the other source. As for what exactly is called "Dial's algorithm": different sources will disagree on the details, obviously, just as they disagree on what exactly is a bucket queue, but they agree that it is Dijkstra+bucket queues. I don't think the disagreement over details of nomenclature is significant enough to warrant mentioning in the article. —David Eppstein (talk) 20:02, 6 July 2021 (UTC)
    • It doesn't describe it, but as I said above, it alludes to it. Anyways, re the cite, I'm not even sure what you're trying to argue here. Does the citation verify any of the propositional content of the sentence to which it attaches? If so, what part(s) of the sentence? If not, is your argument that it's fine because there are other citations that do? Colin M (talk) 22:45, 6 July 2021 (UTC)
      • It verifies the claim that the modular optimization can save space, if not in as much detail as some of the other sources. But it's not necessary here. Rather than removing it altogether, I used it to source a claim that the priorities in this application are monotone. —David Eppstein (talk) 06:05, 7 July 2021 (UTC)
    • As for what exactly is called "Dial's algorithm": different sources will disagree on the details, obviously I don't see why that's obvious. We're talking about more than just a difference in superficial details. Colin M (talk) 22:45, 6 July 2021 (UTC)
      • It's an optimization. You can fail to make the optimization and it's still the same basic algorithm. If I omit the ketchup from my hamburger, it's still a hamburger. It should not be surprising that the exact scope of a name turns out to be a fuzzy thing when looked at carefully: if I omit the bun, is it still a burger? Or if I put a piece of fried chicken into it instead of a beef patty? You'll get different answers from different people, and yet we're still capable of having a reasonably coherent hamburger article that doesn't even mention the purists who will tell you that that's not a hamburger. Anyway, Bersekas and (new source) Festa clearly describe the algorithm without the modular optimization as being Dial's, and then mention the optimization later as a useful thing to do but not as a defining part of the algorithm. Varghese is more dogmatic, it seems. But I don't see this as being a fundamental-enough disagreement to require us to point out the differences and call out which sources use which variation. —David Eppstein (talk) 06:05, 7 July 2021 (UTC)
        • I question the value of this analogy. Food items like hamburgers are not subject to formal definitions in the way that mathematical entities are. If different sources give different definitions of trapezoid or natural number, it's important to call that out. I agree that some details in which versions of an algorithm differ are unimportant (e.g. whether you do an equality check at every iteration of binary search), but I don't think a difference that affects the asymptotic runtime can qualify as such. Colin M (talk) 17:52, 8 July 2021 (UTC)
        • That said, I'm fine with not mentioning the ambiguity if you think that Varghese is an outlier here. Colin M (talk) 17:53, 8 July 2021 (UTC)
          • Um, it doesn't affect the asymptotic runtime. It affects the memory usage. —David Eppstein (talk) 17:59, 8 July 2021 (UTC)
            • Okay. I still think that's more than a superficial difference. I don't want to hyperfocus on this detail - it's not really grounds for a GA fail - but I still think that, unless Varghese is alone in their differing definition, something like an efn mentioning the name ambiguity would be helpful. But your call. Colin M (talk) 18:20, 8 July 2021 (UTC)
• Both the shortest path and set cover applications (and maybe some of the others?) involve a "priority update" operation. This op is now included in the "Example" section, which is great. But a naive implementation of the op would involve a linear search of a bucket, which (according to my understanding, which may be wrong) would preclude the overall runtimes that we give for the algorithms. So they have to rely on some cleverness to implement updates efficiently. Seems like this would be worth mentioning.
  • This is really a question about how you implement the container for the bucket, and not about bucket queues per se. It is out of scope for this particular data structure. If you use linked lists as your container you have to have some way of going from the item to its linked list object. If you use dynamic arrays as your container you have to have some way of going from the item to its index in the array. If you are using a dynamic set then you get this operation encapsulated within your set data structure and don't have to worry about it but you might pay more for the time of individual dynamic set operations. If you are using a binary heap rather than a bucket queue you have to have some way of going from the item to its position in the array representing the binary heap. This is all a standard matter of algorithm engineering that is true of many algorithms and data structures in general and is not specific to bucket queues. —David Eppstein (talk) 19:35, 6 July 2021 (UTC)
• Somewhat related to the above point: we present deletion of an arbitrary element as a basic operation in the "Basic data structure" section, but this op isn't actually used in any of the algorithms/applications described in the article (except insofar as it may be implicitly used as a subroutine of the update-priority operation). So is this actually an important component of the interface of the DS? (And if so, could that be cited?) Conversely, is the priority-update operation an important one that we're failing to cover?
  • I added the change-priority operation (needed for most versions of Dijkstra) to the operations, describing it as a delete and reinsert (so it makes the delete necessary as well). —David Eppstein (talk) 19:37, 6 July 2021 (UTC)

Also, one higher-level comment: I'm a bit concerned that I've encountered failed verifications on both read-throughs - and I have been far from exhaustive in my checks. I'm not sure what to suggest at this point other than maybe doing a review of citations to confirm they match the text? Colin M (talk) 18:49, 6 July 2021 (UTC)

By the way, please ping me when you're ready for me to take another (hopefully final) pass. Colin M (talk) 22:47, 6 July 2021 (UTC)

@Colin M: Ok, we seem to be back in a state where I've addressed all the points above (but the discussion is getting messy enough that I might well have missed one; please let me know if I have). So please take another look. —David Eppstein (talk) 06:07, 7 July 2021 (UTC)

Round 3

As you've noticed, I added a couple more replies above (including one reviving a topic from the first round of comments which I mistakenly thought was resolved).

A couple more issues of some substance:

• or, by maintaining a pointer to the most recently found bucket, in time proportional to the difference in priorities between the results of successive searches. This isn't quite accurate, is it? Since the stored index can also be updated in response to an insertion, not just a find-min? Also, I think a reader might be confused at this point since, in the general case, such an optimization doesn't seem to change the asymptotic time complexity. Up to you how you want to patch this, but my suggestion would be to subtract rather than add detail. e.g. even just something like "though this can be improved in problems where the minimum priorities form a monotonic sequence".
  • Simpler fix is to say "operations" in place of "searches". —David Eppstein (talk) 18:45, 8 July 2021 (UTC)
• Edelkamp is cited for the alternative name "bucket priority queue", but they use the name "1-level bucket".
  • I quote from the footnote as already given: "See also p. 157 for the history and naming of this structure." On p. 157 they use the phrase "bucket priority queue" for a general class of priority queues, among which the one described here is the 1-level one. Again, the naming of complex mathematical constructions such as algorithms is often imprecise. —David Eppstein (talk) 18:48, 8 July 2021 (UTC)
    • Are you referring to the first sentence of 3.7 on page 157? Because the full quote is "Dial (1969) has invented the 1-Level Bucket priority queue data structure." (formatting in original) Some quotes from the chapter on the data structure:
      • A simple implementation for the priority queues is a 1-Level Bucket.
      • Example for a 1-Level Bucket data structure.
      • Updating the key in a 1-Level Bucket.

    There is as much justification for saying this text calls it a "bucket priority queue" as there is for saying it calls it a "bucket data". Colin M (talk) 21:11, 8 July 2021 (UTC)

    That's...remarkably pedantic, even for a Wikipedia editor. But fine, I replaced the source with Henzinger et al, which uses the same phrase less ambiguously. —David Eppstein (talk) 21:18, 8 July 2021 (UTC)

    If you don't think it's wrong, then just don't change it. Don't act like you're making an unnecessary change just to placate me, while firing off a pot shot. Colin M (talk) 22:44, 8 July 2021 (UTC)

    I think the replaced source is clearer about this. I wouldn't have replaced it if I didn't. —David Eppstein (talk) 23:40, 8 July 2021 (UTC)

Also, a couple totally optional suggestions:

• Bucket queues are also called... the content beginning here seems unrelated to the previous two sentences. Maybe start a new para?
  • The whole paragraph ties together related problems (pigeonhole sort, calendar queues) and alternative names. The two topics are tangled together by the quantization of real numbers used both in the related calendar queue and in the context of some of the names, so teasing them apart into separate paragraphs would lose that connection. Also the paragraph is not overlong currently so splitting would make two very short paragraphs. I think it's a little better as a single paragraph. —David Eppstein (talk) 18:53, 8 July 2021 (UTC)
• Would be nice if variables had the same formatting in the 'Example' section as they do in the rest of the article.
  • Reformatted. —David Eppstein (talk) 18:45, 8 July 2021 (UTC)

Colin M (talk) 18:35, 8 July 2021 (UTC)

@Colin M: I don't want to annoy you by too-frequent pings, but I think we have again (actually a couple of days ago) reached a state where revisions have stabilized and all points above have been responded to. If the delay in updating merely means you are occupied somewhere else and were planning to get back to this after you had time, then don't worry about rushing; I can wait. —David Eppstein (talk) 06:57, 12 July 2021 (UTC)

 Passed Irritation makes pearls Colin M (talk) 22:54, 12 July 2021 (UTC)