Win a copy of Reactive Streams in Java: Concurrency with RxJava, Reactor, and Akka Streams this week in the Reactive Progamming forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Ganesh Patekar

Singled Linked List vs Array

 
Ranch Hand
Posts: 266
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just a curious question: is the linked list representation of a polynomial better than the array based representation?
 
Saloon Keeper
Posts: 6227
58
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
 
Saloon Keeper
Posts: 10657
227
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're saying it as if those are the only ways to store a polynomial. Personally I'd probably use a LinkedHashMap.

Why are you wondering about this? ArrayList should be your default choice, unless you have a very particular reason for using a LinkedList. What reason do you have?
 
Stephan van Hulst
Saloon Keeper
Posts: 10657
227
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:Are you planning on doing a lot of insertions or deletions in the middle of the list?


This is not enough. For LinkedList to be effective, a modification must be spatially proximal to the previous, so that it doesn't take a lot of time to move the iterator from the previous position to the next. Simply inserting at an index multiple times is just as disastrous for performance as performing multiple searches.
 
Marshal
Posts: 65782
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You would therefore have to use myIterator.add(xxx) rather than myList.add(123, xxx), wouldn't you.
 
Stephan van Hulst
Saloon Keeper
Posts: 10657
227
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes. The only way to make a LinkedList outperform an ArrayList is by modifying it through the iterator.
 
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:
This is not enough. For LinkedList to be effective, a modification must be spatially proximal to the previous, so that it doesn't take a lot of time to move the iterator from the previous position to the next. Simply inserting at an index multiple times is just as disastrous for performance as performing multiple searches.



No. That's true for ArrayList, where the entries are stored in an array - contiguous cells in memory. But the "space" in a LinkedList consists of randomly-located cells joined by pointers. Inserting multiple entries in the middle of an ArrayList requires shifting the following cells in RAM - or worse, creating a whole new array and copying the entire list.  Inserting multiple entries in a LinkedList requires only breaking the current links, creating a new cell and melding it into the chain for each entry. That's 4 pointer adjustments total compared to n pointer adjustments (best case) for an ArrayList (n=number of entries in the list currently at or beyond the insertion point.

Stephan van Hulst wrote:Yes. The only way to make a LinkedList outperform an ArrayList is by modifying it through the iterator.



That is a meaningless statement. "Performance" depends on context. As I said, it's more efficient (performant) when doing insertions and deletions to use a LinkedList, but it's more performant to randomly access elements in an ArrayList. I'd bring up that hoary old story of when I ended up using a Shell-Metzner sort on a major processing system because the standard input data order was mostly-sorted-except-for-a-few-items-in-the-middle. Which is worst-case condition for the more "performant" Quick and Heap sorts. But I've covered that in detail enough times already.
 
Stephan van Hulst
Saloon Keeper
Posts: 10657
227
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:Inserting multiple entries in a LinkedList requires only breaking the current links, creating a new cell and melding it into the chain for each entry. That's 4 pointer adjustments total compared to n pointer adjustments (best case) for an ArrayList (n=number of entries in the list currently at or beyond the insertion point.


But only if you already have a reference to the link that needs to be broken. If not, then you have to first iterate through half of the list to find the link to break. This is why you need to keep a reference to an iterator around. Calling LinkedList.add(int, E) is almost never faster than calling ArrayList.add(int, E), even when inserting in the middle of the list. And when using an iterator to perform the insertions, the insertion points must be close enough to each other (by index, not by memory location) that the iterator doesn't end up iterating through half of the list anyway.

That is a meaningless statement. "Performance" depends on context. As I said, it's more efficient (performant) when doing insertions and deletions to use a LinkedList, but it's more performant to randomly access elements in an ArrayList.


What context? Literally the only time a LinkedList is consistently faster than an ArrayList is when performing multiple modifications around roughly the same insertion point using an iterator. I'll write a benchmark later to illustrate this.
 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Context" When you are " when performing multiple modifications around roughly the same insertion point". Remember what I said about the Shell Sort? For a case of abcdeyxfghi..., one of the partitioning sorts would end up dumping everything in a single partition and tossing it back and forth over and over again.

And what's with this obsession with an iterator? If you modify a List while iterating it, it's quite possible you'll throw a ConcurrentModificationException. Actually, offhand, I'd say it's more likely to happen on an ArrayList than a LinkedList, though I'd have to check the docs to be sure.

A very popular pair of LinkedList subclasses are the Stack and the Queue. Both of these constructs don't have any search time to speak of in their primary functions, since the first - and often the last - nodes of a doubly-linked list are anchored in the List object itself.

If you already have a Node in a list and you want to insert, remove, or modify other nearby nodes, you don't have to start at the beginning of a LinkedList and run your way upwards. You already know where you are, and you can chase links from there if it's more efficient. Only truly random node access carries major penalties.

Even random node access may or may not be the deciding factor on whether a LinkedList is a suitable collection type for a given task (context). If the list is less than a dozen or so elements and is referenced infrequently, the extra overhead is likely to be negligible in the larger performance metrics. If there are lots of insertions and deletions, in fact, the insert/delete speed may utterly dwarf the access speed benefits of an ArrayList. And if it's really a problem, perhaps the better solution is a TreeSet or TreeMap.

And, speaking of the virtues of ArrayLists, a straight array is "better" by simplistic metrics than an ArrayList, since it has no insert/delete operations at all, and therefore doesn't have to endure the overhead of expanding and repacking itself.

Blanket assertions give me stomach-aches.
 
Stephan van Hulst
Saloon Keeper
Posts: 10657
227
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:And what's with this obsession with an iterator? If you modify a List while iterating it, it's quite possible you'll throw a ConcurrentModificationException.


I'm talking about Iterator.remove() and ListIterator.add(E). These methods were designed explicitly with concurrent modification in mind. Here's how you insert multiple items in the middle of a LinkedList:

This code finds the insertion point between "C" and "X" once, and then performs three insertions.

Now consider:

This code finds the insertion point between "C" and "X" and inserts "K", then finds the insertion point between "K" and "X" and inserts "L", and finally finds the insertion point between "L" and "X" and inserts "M". That's three searches instead of one, each search running in linear time with regards to the size of the list. The fun part is that for most real-life list sizes, resizing the array of an ArrayList is faster than the combined cost of searching each insertion point individually and then creating objects for the new nodes.

If you already have a Node in a list and you want to insert, remove, or modify other nearby nodes, you don't have to start at the beginning of a LinkedList and run your way upwards.


So how do I do this as a programmer using LinkedList, without having access to the internals of the list, and without using ListIterator?

If there are lots of insertions and deletions, in fact, the insert/delete speed may utterly dwarf the access speed benefits of an ArrayList.


When I remember how to use JMH I will write a benchmark and get back to this. I recall that it requires LOTS of insertions though.
 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That was simply awful.

If you want to insert a sublist into a list, you don't insert element by element, you insert the sublist in a single operation. I'm pretty sure that java's List class has a method for that. I mean it's built into some languages. Python, I think, for one. I believe it's the addAll() method in Java.

You CERTAINLY don't search for the insert point for each insertion. Even using brute force, once you've located the insert point, you either insert each item at that point (push) or use the last-inserted item as the insertion point for the next item (extend).

And WTF is JMH?

 
Stephan van Hulst
Saloon Keeper
Posts: 10657
227
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:That was simply awful.

If you want to insert a sublist into a list, you don't insert element by element, you insert the sublist in a single operation. I'm pretty sure that java's List class has a method for that.


I simply meant to illustrate how you would perform multiple insertions that are close to each other, not necessarily right next to each other. If it makes it easier, imagine that instead of what I did the task was to interleave the inserted elements.

You CERTAINLY don't search for the insert point for each insertion. Even using brute force, once you've located the insert point, you either insert each item at that point (push) or use the last-inserted item as the insertion point for the next item (extend).


Can you write a snippet that demonstrates what you mean? Let's say you have a list with a thousand elements, and you want to insert three new elements at indices 498, 500 and 502.

And WTF is JMH?


It's a benchmarking tool that takes care of the finicky stuff like JIT optimization.
 
Campbell Ritchie
Marshal
Posts: 65782
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:That was simply awful. . . .

If it is awful, then it is a failing with the implementation of a linked list.
Stephan is correct that you need a reference to a particular list node in order for deletions and additions in a linked list to run quickly. That particular implementation only allows access to a “current node” via the iterator. Maybe they didn't think anybody would have to use addAll() on a linked list using its iterator, but iterators don't seem to have an addAll() method. Maybe that is a shortcoming which should be remedied. But that is the state of play just at the moment.
 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What was awful was the sample code. It's doing redundant work. It's like fetching the same web page 100 times to read 100 rows of data. When a list is processed the way lists were designed to be processed, it's significantly more efficient.

And there's this thing called a ListIterator. It has an addAll() method.
 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:
Can you write a snippet that demonstrates what you mean? Let's say you have a list with a thousand elements, and you want to insert three new elements at indices 498, 500 and 502.




How about an English explanation? Now, granted, once a linked list has 1000 elements, it probably should be something other than a list, but sometimes there are good reasons for large lists, so I won't consider the issue to be overly contrived.

The hard part is, of course, getting to node #498. For a an ArrayList, of course, this is a doddle, but there are other types of lists, including Skip Lists where you can have chained elements and internal mechanisms will shortcut the process considerably. That's the advantage of abstract collection classes.

OK, I'm going to stop here and note that when talking about efficient use of linked lists that I've been using as my mental reference the raw implementation of a linked list, where you have actual access to the nodes - including their links. This is what I worked with on the Amiga OS. And the Amiga Exec is so riddled with doubly-linked lists that list primitives are actually available as OS system calls.

But Java, just from a quick check, isn't allowing direct access to linked nodes (unlike the elements in HashMap). So oops.

Almost.

Here it is:


I believe that should do it, and do so a LOT more efficiently than starting from 0 each time.

Note that having the listIterator(start) method allows subclasses (such as skip lists) the latitude to run skip chains and avoid the overhead of simply iterating from 0.
 
Rancher
Posts: 3369
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Yes. The only way to make a LinkedList outperform an ArrayList is by modifying it through the iterator.



Well, the big exception to this statement would be if you're inserting or removing near the start of the list.  Then LinkedList does great.

I do agree with the point that if you want to get some benefit from using LinkedList in the middle, you need to be using the ListIterator.  To me it makes the most sense if you're going to be iterating through the list anyway, and need to be able to delete or insert additional lines as you go.  I've probably found myself doing that about five times in the last twenty years.  (Once was in Advent of Code last year.)  More commonly, I was creating a new list anyway, or writing to a file, and any edits along the way would be sent only to the new list, not the original.

For the original question,  I can't imagine frequently needing to modify a polynomial like that. I'd probably just go with a double[] to represent a polynomial in most cases.  The LinkedHashMap is good if the polynomial is sparsely filled though - i.e. relatively few few non-zero coefficients.  
 
Stephan van Hulst
Saloon Keeper
Posts: 10657
227
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tim, isn't that what I did in my first example snippet? Granted, that's not what I would do when I had to add an entire collection at some index, but that wasn't the point of it. The point was that the iterator acts as a reference to the list node.
 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In low-level terms a LinkedList is often comprised of 2 types of objects:

1. The list header, which points to the first (and possibly last) nodes in the list.

2. The list nodes, which contain forward (and possibly backward) links and the node value.

You can make a list without a header, but you get more flexibility when you have one and this appears to be how Java manages LinkedList. Which I just confirmed is a doubly-linked list, and not, say, a singly-linked list.

Since LinkedList's raw nodes are not visible via its API, the ListIterator serves as a stand-in for a node reference. It augments that by also referencing the list header, so that operations such as adding an element to the end of a list are reflected in the list header's references as well. It's an Iterator officially and functionally, but in reality, it's a proxy for a node reference.

Your first example "failed" because the simpler, more efficient code is:


Your second example is the one that appalled me, though, since it requires potentially running the list up to find the i'th element for each add, assuming that List.add() doesn't cache previous searches. And I doubt it does. You're at liberty to make a subclass to rectify that though.

And it's really not cricket to use "i" as an iterator in one example and as an index in another. I read sloppy even without curveballs like that.
 
Rancher
Posts: 1180
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Revisiting the original question...

Ana Yo wrote: Just a curious question: is the linked list representation of a polynomial better than the array based representation?



I agree with what I think Carey was implying - the answer depends on a few factors:
- Is there an absolute maximum and minimum exponent for the terms?
- What is the mix of operations you'll be performing?  Will you be doing many (or even any) insertions, deletions or updates once a polynomial is created?
- What do you define as "better"?  Easier to program?  Faster to execute a thousand operations?  Uses less memory?

For instance, if you're writing a class for a non-honors level high school class, the maximum exponent may be 6 and the minimum 0, at least for 95% of the cases.  It may also be that once a polynomial is calculated (maybe by the multiplication method of the class), it is never modified.  i.e. Instances of the class are value objects.  In such a case, I would guess that using plain old arrays would be easier to program and faster to execute than if any of the more complex data structures were used.
 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ryan McGuire wrote:Revisiting the original question...



Answering the original question. What a concept!

Actually I didn't understand the original question. I just got irked at the incidental assertions.

You can use a sequential collection to represent a polynomial in the form a^0+b^1+c^2... with the first element holding the value of a, the second b, and so forth. And assuming that you never want to change the number of terms, there's really no beating a simple array. And I can't think of a reason for insertion/deletion of terms unless you're creating a program on the order of Mathmatica.

If you want to hold the values obtained from applying a polynomial to another polynomial, that depends. The most common cases in computing where that is done is to create Error Checking (and optionally Correcting - ECC) codes or to encrypt data. In which case, you typically either stream the bits of the data to be transformed (shift/XOR) or you apply the polynomial to a fixed-size buffer (often being a padded slice of a larger data set).

Here again, the internal storage seems to mitigate towards an an array. If  applying the polynomial to a data buffer, that buffer would typically be an array of bytes,
 
Mike Simmons
Rancher
Posts: 3369
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:Answering the original question. What a concept!



This may have been lost in the noise...

Mike Simmons wrote:For the original question,  I can't imagine frequently needing to modify a polynomial like that. I'd probably just go with a double[] to represent a polynomial in most cases.  The LinkedHashMap is good if the polynomial is sparsely filled though - i.e. relatively few few non-zero coefficients.

 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mike Simmons wrote:

Tim Holloway wrote:Answering the original question. What a concept!



This may have been lost in the noise...

Mike Simmons wrote:For the original question,  I can't imagine frequently needing to modify a polynomial like that. I'd probably just go with a double[] to represent a polynomial in most cases.  The LinkedHashMap is good if the polynomial is sparsely filled though - i.e. relatively few few non-zero coefficients.



Yeah. Although it would have to be a pretty complex polynomial. The ones used for most IT tasks have relatively few degrees, so the fact that they're also sparse wouldn't really make much difference.

Come to think of it, IT polynomials tend to have binary coefficients, so a simple bitmap suffices - and is efficient for shift/xor to boot. And you can fit a lot of terms into a bitmap.
 
Ryan McGuire
Rancher
Posts: 1180
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mike Simmons wrote:

Tim Holloway wrote:Answering the original question. What a concept!



This may have been lost in the noise...

Mike Simmons wrote:For the original question,  I can't imagine frequently needing to modify a polynomial like that. I'd probably just go with a double[] to represent a polynomial in most cases.  The LinkedHashMap is good if the polynomial is sparsely filled though - i.e. relatively few few non-zero coefficients.



Ahh yes... I scanned the conversation but most of it was, I hate to admit, tl;dr.  A double[] was indeed what I was getting at.
 
Mike Simmons
Rancher
Posts: 3369
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:Come to think of it, IT polynomials tend to have binary coefficients, so a simple bitmap suffices - and is efficient for shift/xor to boot.



Interesting - what sort of examples are you thinking of here?  I was mostly imagining things like Taylor series for functional approximation, which pretty much require real numbers.  But my academic background is physics - it was a long time before I accepted there was any use for integers at all, as opposed to reals.
 
Tim Holloway
Saloon Keeper
Posts: 21128
131
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I believe that the polynomial for Ethernet ECC (as an example) is x^12+x^11+X^3+X^2+x+1. Hashes like MD5 are polynomial as well, I believe.

I hadn't considered series polynomials. Aren't most of them non-terminating? Computer math libraries simply make up the elements on the fly rather than attempting to store them statically. They also scale where it can cause the series to converge more rapidly.
 
Mike Simmons
Rancher
Posts: 3369
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:I believe that the polynomial for Ethernet ECC (as an example) is x^12+x^11+X^3+X^2+x+1. Hashes like MD5 are polynomial as well, I believe.



Interesting... I know zilch bout the internals of these.  Now I'm intrigued, thanks.

Tim Holloway wrote:I hadn't considered series polynomials. Aren't most of them non-terminating?



Typically, yes.  But there are enough cases where the higher terms become successively more negligible, that you can justify limiting the number of terms to five, ten, twenty, something manageable.

Tim Holloway wrote:Computer math libraries simply make up the elements on the fly rather than attempting to store them statically.  They also scale where it can cause the series to converge more rapidly.



For standard well-defined functions, yes.  And for Taylor/ series that's generally what we're talking about.  But you could also be doing curve-fitting for an arbitrary set of data points.  Or finding a solution to some differential equation that has no known analytic solution, but we can try something that looks like a polynomial of arbitrary complexity, and see how close you can come to a solution.  Or some other random complex problem that doesn't match standard libraries.  There are lots of potential applications for polynomials as approximations to something else we don't fully understand.
 
girl power ... turns out to be about a hundred watts. But they seriuosly don't like being connected to the grid. Tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!