CODEWITHSUNDEEP
javaalgorithm
java_pill
java_pill

Reputation: 843

Java algorithm to slice a list

I'm trying to slice a list (call this input list & it contains Java double data type elements) in multiple parts (sub lists). The size of the sub lists can be unequal by a small number. Each part (sub list) serves as an input to another program. The size of the input list is a variable with a maximum size of 10,000 i.e. it can be as small as 1 or 2 or 3 and as big as 100 or 10000 or any number under 10000.

What is the best way to slice such a list into multiple parts? I have been considering the 3h+1 distribution by Donald Knuth in designing gaps for shell sort. However, I'm not sure whether it would be appropriate. Appreciate your help.

Thanks!

Upvotes: 0

Views: 843

Answers (2)

Larry Watanabe
Larry Watanabe

Reputation: 10184

To expand on the answer the optimal value of M,

Assume there is some cost function C associated with processing a list of size M.

Then you want to minimize the function

TotalCost = M * C(N/M) + overhead

where overhead is the cost of splitting up the list.

I think for most applications there wouldn't be much difference for different values of M, so there is no point in splitting it up.

The situation where it would be useful is if you have multiple processors so and you can hand off the sublists to a different processor. In this case, the cost function would be more like

TotalCost = C(N/M) + overhead if M < number of processors

so you should choose M to be close to but less than the number of processors.

Upvotes: 2

Larry Watanabe
Larry Watanabe

Reputation: 10184

Unless I'm misunderstanding this question, this seeems easy.

Given a list of size N, to create M sublists, where M < N,

  1. create M-1 lists of size K = N/M
    (rounding down)
  2. create a list of size M - (M - 1) * K

Then

  1. copy the first K elements to the first list
  2. copy the next K elements to the second list,
  3. and so on,
  4. finally copy the last M - (M - 1) * K to the last list.

Upvotes: 2

Related Questions