Martin Vashko

For starters, could you share the DDL statement for the entire table here? You can get it from some SQL client tools, such as HeidiSQL (which should come with MySQL by default, I think).

It looks like the sent column is part of some foreign key. We need to find out which one it is.

Campbell Ritchie wrote:Are you suggesting that the documentation comments might be mistaken? I am aware of errors in other documentation comments, particularly older ones.

I'd say imprecise, not mistaken. It just doesn't distinguish between two different add operations.

Supporting argument: if shifting elements was considered an O(1) operation by the documentation author(s), the remove(int index) operation should be considered O(1) too. Which it isn't.

Campbell Ritchie wrote:Does ArrayList have an insert() method? If you use ctrl‑F‑insert, it finds the descriptions of the various add(...) methods.

Damn!

No, it  doesn't. It has an add(E element), which adds to the end of the list, and add(int index, E element), which I somehow though was called insert.

ETA: Now, the Javadoc doesn't distinguish between the to add methods when discussing the amortized constant time. In the second paragraph I cited above, they link the amortized constant time characteristics to the growth of the buffer. I still maintain that add(E element) is O(1) and add(int index, E element) is O(n).

I looked at the output of the code.
Close to what I want.

That's good news! Can you tell us how is this solution different from what you need?

You've already asked this question here and it looks like you were getting close to what you need in that other thread. Please continue the discussion in the original thread.

Paul Clapham wrote:If you use 1 (because copying the 64 elements is "blindingly fast" as Martin said) then you end up with O(1) -- the copying occurs only for powers of 2 so the cost is 1/2 + 1/4 + 1/8 + ... (That's what they mean by "amortized constant time").

I don't think this is what they mean by amortized constant time. Even when the copying does take more time as the arrays get longer, we still get O(1) per addition of one element:

Paul Clapham wrote:But if you use 64 then you end up with O(log N) -- the cost is 2/2 + 4/4 + 8/8 + ... (as the mathematicians say, the proof of this is "left as an exercise for the student").

This this is the cost of adding N elements. If you want the cost of adding just one element, you get O(N/N) --> O(1).

Campbell Ritchie wrote:Thank you, Martin; that would be linear time then. But why does ArrayList say amortised constant time, then?

They speak about the growth of the ArrayList, not about inserting elements (emphasis mine):

JDK 13 doc wrote:The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

So, add operation is O(1). All the remaining ones (including insert) are O(n).

Campbell Ritchie wrote:But insertion into an array list is usually regarded as amortised constant time

I might be mistaken, but I believe the amortized constant time only applies to the reallocation of the underlying array when the list grows. The new array is allocated in increasing size increments, which means that as the array grows, the reallocations get both more expensive and less frequent, converging to a constant value over time.

Insertion into a random position needs to shift all following elements, and this operation, although probably blindingly fast (there's the REP MOVS instruction, if I'm not mistaken), they will grow a wee bit longer as the array grows.

Piet Souris wrote:Two other quick questions:

1) are the letters always consequtive? Or can we have, say, 1A, 1C, 1Q?
2) are the letters always in alphabetic order, like 1A, 1B, 1C? Or is 1C, 1A, 1B possible?

Sorry if these questions are already answered, I might have missed them.

1) They may or may not be consecutive. When they are, all consecutive items in a sequence are merged using brackets, as shown in the first post.
2) The list of strings is sorted before being processed. Now this might pose a problem: "8A, 9A, 10A" would be sorted into "10A, 8A, 9A", making sequence detection more complicated.

Junilu Lacar wrote:So how does 300A, 301B, 302C get merged? Would it be [300-301][A-C]?

Assuming this is true, what would we do with this sequence: 300A, 300B, 300C, 301A, 301B, 301C, 302A, 302B, 302C?

Edit: and why not [300-302][A-C]?

Janeice DelVecchio wrote:Java with spring boot and poi. Could have been done in any language that has a library for word doc. If it were docx, I would have used straight xml traversal.

Thanks, that makes sense. I guess I spent too many years cobbling up makeshift tools to manipulate Office files using VBA...

Jeanne Boyarsky wrote:We are writing a book about Java. Using another language on the book would be heresy

Good point!

Is this a homework, or a real-world problem? I ask because in a real-world problem, I'd expect that the example you listed in the first post might not represent all possible patterns in the input data.

You mentioned "[8-11]" earlier. Does it mean that "Z8", "Z9", "Z10" and "Z10" will be merged into "Z[8-11]"? Even if the token length doesn't match?

I understand that all trailing digits are processed as a token. Therefore, "ABC1234" and "ABC1235" will be merged into "ABC[1234-1235]". What about consecutive letters? Will "123AZ" and "123BA" be merged into "123[AZ-BA]" (because, assuming an English alphabet, BA is the next item in sequence after AZ). Similarly, should "8Z", "8AA" be merged into "8[Z-AA]"? (See how columns in Excel beyond the first 26 are named if you have trouble to understand these two examples.)

I still don't understand why "51/1" and "51/2" in the example weren't merged into "51/[1-2]". Did you make a mistake in your original post, or is it part of the requirement?

What we know so far:

Only the trailing part of the string has to be processed. The entire trailing part contains either digits or letters.

Questions:

What about uppercase and lowercase letters - are they the same or different? Is it ok to transform "a" and "B" to "[a-b]"? Or "[A-B]" Or not at all?

The trailing part is made of all consecutive digits/letters found at the end of the string? Consider "1234" and "1235". What's the desired output: "[1234-1235]" or "123[4-5]"?

Does the trailing part contain more than one letter at all? Consider the sequence "A01", "A02", ..., "A30". Is "A[01-30]" the desired output?

"51/1" ve "51/2" "51 / [1-2]" No need to edit it.

Sorry, I don't understand this. Can you explain it in more detail, please?

Welcome to the Ranch!

I think we need more precise specification of the requirements. Generally, the input strings need to be split into parts on which the detection of consecutive ranges will happen. For example, "4" contains just one part. "2A" contains two: "2" and "A". "583-585D" contains how many? I can think of "583", "585" and "D", but perhaps "583-585" needs to stay together. What are all the rules that apply here?

Should he ranges be merged only for the last part of the string, or for the other parts too? For example, should "3A", "4A" and "5A" be merged into "[3-5]A"?

Why isn't "51/1" and "51/2" merged into "51/[1-2]" in the example output?

Without precise specification, no one can even tell whether a solution does meet all the requirements or not.

S Fox wrote:i could avoid doing any sorting at all if i insert each result into an arraylist in the correct position as soon as it's generated. the list must be locked to do this. i could use a binary search to find where to insert at. this should prevent needing to traverse the list. the insert will then shift everything down and dynamically resize the array if needed. each search/insertion will need to happen about 5k times per second per worker.

My solution would be to have two different data structures: one to keep the output of your computations, and another just for the data to be shown in the GUI. The first one can be kept unsorted, and when the computation finishes, it could be dumped into a file for later use (I have no idea what you plan to do with all the things your program computes). Perhaps you could use one collection per worker thread and only merge it once all is done, avoiding any synchronization between worker threads.

The collection for the GUI would be a list that would keep N best results found so far. When a new result is produced, the worker threads would just check whether the new result makes it into the list (so it would be compared just with the last element of the list), and if it did, it could be inserted into the list (perhaps using binary search) and any items beyond the first N would be deleted. The comparison would be done on worker threads (and you could actually maintain the threshold value separately from the list and use volatile variables and/or some lightweight synchronization to access it), but inserting the new value into the list would be done on a GUI thread. Inserting new values would become quite rare fairly quickly, therefore consuming a fraction of CPU time.

The assumption behind all this is that the user wouldn't be interested in browsing more than N intermediate results while the computation runs. I've seen some software working similarly (chess engines, for example, often show just the best line of moves found so far, despite checking thousands or millions of positions per second).

Are you sure you want to create a new instance of Random every time you need a random number?

i didn't think about the cost of making this new object every time

That's only part of my concern. The other concern is that a sequence obtained this way might have inferior random properties compared to a sequence made from a stable Random instance.

also i just noticed that there's a special randomization object for multi-thread apps. i think i should be using that one instead.
ThreadLocalRandom

That's a good idea. Behind the screen, ThreadLocalRandom effectively provides a separate instance of Random sequence for each thread. I guess it can be in some ways better than allocation your own Random in each thread; not sure how though.