Algorithms Discussion Boards

First Prev Next

Re: My implementation of Eratosthenes sieve is horribly slow. But why?

Dave Kreskowiak8-Sep-20 6:46

Dave Kreskowiak

8-Sep-20 6:46

It's slow because you're using a List instead of an array.

Every time you remove an entry from the List, the remaining values in the list after the item removed have to be moved down one position. Depending on the size of the List, that can take quite a bit of time.

Use an array of flags instead of integers.

Asking questions is a skill
CodeProject Forum Guidelines
Google: C# How to debug code
Seriously, go read these articles.

Dave Kreskowiak

Re: My implementation of Eratosthenes sieve is horribly slow. But why?

Richard Andrew x6422-Sep-20 10:36

Richard Andrew x64

22-Sep-20 10:36

Question:

I always thought .NET Lists were implemented as linked lists. After all, what would differentiate them from arrays?

The difficult we do right away...
...the impossible takes slightly longer.

Re: My implementation of Eratosthenes sieve is horribly slow. But why?

Dave Kreskowiak22-Sep-20 16:25

Dave Kreskowiak

22-Sep-20 16:25

Nope. Internally, it's an array. You can see it in the reference source: Reference Source - List<t>[^]

What differs it from a normal array is just managing the array size and making it easy to add/remove items to the array. If the array gets too full, it automatically creates a new, larger array and copies the items over to it.

Asking questions is a skill
CodeProject Forum Guidelines
Google: C# How to debug code
Seriously, go read these articles.

Dave Kreskowiak

Re: My implementation of Eratosthenes sieve is horribly slow. But why?

Patrice T18-Sep-20 19:51

Patrice T

18-Sep-20 19:51

Member 14932873 wrote:
Can someone explain to me, why my solution is slower:

Your code is slow because it seems your code combine all the worst choices.
- you are continuously resizing the list, it is very time expensive.
Use an array allocated once.
- you are checking if a number is multiple with a modulo, it is very expensive too.
When you check for a prime, start from the prime and add repeatedly the prime to scan all multiples.

Speed of operations: fast to slow
Addition, subtraction < multiplication, squaring < division, modulo, square root

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

How can I remove alternate words from a sentence?

maicart5-Sep-20 22:27

maicart

5-Sep-20 22:27

I'm building a language learning website. In one of the exercises the user has to guess the missing words. For example in the sentence:

What is the weather like? It is sunny today.

My developer has created an algorithm that shows the first and last words of the sentence, while removing the alternate words within it. The result is:

What ____ the ____ like? ____ is ____ today.

However, in a sentence like this:

It is not the entrance, it is the exit.

My developer says that the algorithm does not work because the word "the" is repeated.

I don't understand why the algorithm does not work when words are repeated. They still appear in alternate position, right?

Is there a solution? I could post our current algorithm if necessary.

Re: How can I remove alternate words from a sentence?

Gerry Schmitz6-Sep-20 4:14

Gerry Schmitz

6-Sep-20 4:14

~~It doesn't work because the last sample has an "even" number of words~~. ~~The "last word" would have to be the last 2 words (due to "alternating")~~. Nothing to do with "the".

This adds the "last 2 words" if the word count is even.

string sentence = "It is not the entrance, it is the other exit.";

var words = sentence.Split( new char[] { ',', '.', ' ' }, StringSplitOptions.RemoveEmptyEntries );
List<string> selected = new List<string>();

for ( int i = 0; i < words.Length; i++ ) {
   if ( ( i + 1 ) % 2 > 0 ) {
      selected.Add( words[ i ] );
   }
}  // end for.

if ( words.Length > 1 && words.Length % 2 == 0 ) {
   selected.Add( words.Last() );
}

string result = string.Join( " ", selected );

Console.WriteLine( sentence );
Console.WriteLine( result );
Console.ReadKey();

It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food

modified 6-Sep-20 12:46pm.

Re: How can I remove alternate words from a sentence?

Richard MacCutchan6-Sep-20 6:13

Richard MacCutchan

6-Sep-20 6:13

Gerry Schmitz wrote:
the last sample has an "even" number of words

Really, 9 is even?

Re: How can I remove alternate words from a sentence?

Gerry Schmitz6-Sep-20 6:33

Gerry Schmitz

6-Sep-20 6:33

It's either odd or even that doesn't work. It's early. $Shucks | :-\$

It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food

Re: How can I remove alternate words from a sentence?

Richard MacCutchan6-Sep-20 4:52

Richard MacCutchan

6-Sep-20 4:52

maicart wrote:
My developer says that the algorithm does not work because the word "the" is repeated.

I think you should ask him to explain.

Re: How can I remove alternate words from a sentence?

maicart6-Sep-20 6:23

maicart

6-Sep-20 6:23

I'll talk to him tomorrow. If he does not solve the issue I will paste the algorithm in this thread in case you could help us.

Re: How can I remove alternate words from a sentence?

Richard MacCutchan6-Sep-20 6:41

Richard MacCutchan

6-Sep-20 6:41

I cannot think what could be difficult in a piece of code to remove alternate words from a sentence.

Re: How can I remove alternate words from a sentence?

Richard Andrew x646-Sep-20 8:04

Richard Andrew x64

6-Sep-20 8:04

I suspect it is homework.

The difficult we do right away...
...the impossible takes slightly longer.

Re: How can I remove alternate words from a sentence?

maicart7-Sep-20 1:27

maicart

7-Sep-20 1:27

I just talked to my developer. Actually, there are 2 rules:

1st rule: In case of an odd number of words, the system will show the first and last word and will remove alternate words in the middle. Example:

A pear and an apple.

After the algorithm, the system will show:

A _____ and _____ apple.

2nd rule: In the case of an even number of words, the system will also show the first and last word and will randomly remove any of the alternate clues. Example:

How are you today?

After the algorithm, the result could be rendered either a) or b)

a) How _____ you today?
b) How are _____ today?

My developer sent me a PHP file with a clarification. Here's the link:
ClueAlgo.php - Google Drive[^]

I would appreciate your help if this is a quick fix. If it takes time this could be a paid job, for example on Fiverr.com

Re: How can I remove alternate words from a sentence?

Richard MacCutchan7-Sep-20 1:38

Richard MacCutchan

7-Sep-20 1:38

Sorry, I don't understand what help you are asking for. If you want it changed then tell your developer what he needs to do.

algorithm to place N rectilinear blocks in a ring to minimize total area

rbuchana14-Aug-20 5:21

rbuchana

14-Aug-20 5:21

Imagine having ‘N’ rectilinear blocks of varying sizes. 'N' can be any number (< 1000); and of different but similar sizes.

See here... blocks — ImgBB[^]

I need an algorithm that will place these in a “ring” fashion, such that the area is minimized. White spaces or blank spaces within the ring are fine.

Ring picture... ring — ImgBB[^]

The constraints are…
Each rectilinear block must be placed
Minimize the area (x*y)
Create a ring such as below
Ring implementation

Note that my two pictures don't align exactly, meaning not all the blocks in the first picture are placed in the second. These pictures are only provided as reference/examples.

I’m not a computer scientist by trade. This would seem to be a cost optimization problem, by I’m having a problem wading through the many optimization algorithms out there. Any guidance on which algorithm would be viable?

Thanks!

Re: algorithm to place N rectilinear blocks in a ring to minimize total area

harold aptroot14-Aug-20 8:04

harold aptroot

14-Aug-20 8:04

rbuchana wrote:
Create a ring such as below

What exactly is a ring? Of course I looked at the example, but it could be interpreted differently.

Can the ring look like this? Or this? Maybe like this? Maybe even like this?

Are the coordinates/sizes discrete?

Re: algorithm to place N rectilinear blocks in a ring to minimize total area

rbuchana14-Aug-20 8:19

rbuchana

14-Aug-20 8:19

Door #3... image — ImgBB[^]

Difficult to explain words, but the idea is to have a rectangle in the middle with no protusions.

Coordinates/sizes are not discrete.

Re: algorithm to place N rectilinear blocks in a ring to minimize total area

Gerry Schmitz14-Aug-20 8:22

Gerry Schmitz

14-Aug-20 8:22

Cut the pieces out, move them around until optimum, then reverse engineer into a software solution.

It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food

Re: algorithm to place N rectilinear blocks in a ring to minimize total area

Greg Utas14-Aug-20 8:52

Greg Utas

14-Aug-20 8:52

Are you stating all of the constraints? To minimize the x*y area, it would often be preferable to have two very long sides and two very short ones for the inner rectangle.

For example, say that all rectangles are the same shape and that there are 4n of them. They could be arranged to leave a square in the middle. Let's say the size of the square is a*a and that the four outer areas are also a*a. The x*y area would then be 3a*3a=9a^2.

But instead of leaving an inner square, we can reduce two of its sides by 50% and increase the other two by 50%. Now we have an area of (7a/2)(5a/2) = (35/4)a^2, which is slightly smaller. The size of the inner rectangle is now (a/2)*(3a/2) = (3/4)a^2 instead of a^2.

Robust Services Core | Software Techniques for Lemmings | Articles

Re: algorithm to place N rectilinear blocks in a ring to minimize total area

rbuchana15-Aug-20 9:00

rbuchana

15-Aug-20 9:00

You're correct. There is somewhat of a constraint on the aspect ratio (x/y), but also some flexibility. Meaning it doesn't need to be 50%, but 10% or 90% are probably too much. But no hard limit.

Re: algorithm to place N rectilinear blocks in a ring to minimize total area

Greg Utas15-Aug-20 9:36

Greg Utas

15-Aug-20 9:36

In that case, it's vague (at best) to speak of minimizing the total area.

Robust Services Core | Software Techniques for Lemmings | Articles

Re: algorithm to place N rectilinear blocks in a ring to minimize total area

Greg Utas15-Aug-20 9:45

Greg Utas

15-Aug-20 9:45

If the problem can be stated more clearly, my guess is that it's a variant of the bin packing problem[^]. The article mentions that this problem is NP-hard, which effectively means that the time required to find the optimal solution rises exponentially, although it may be possible to more efficiently find a solution that is known to bounded in terms of how close it is to the optimal one.

Robust Services Core | Software Techniques for Lemmings | Articles

Area vs perimeter

ZhanatanFleming11-Aug-20 4:07

ZhanatanFleming

11-Aug-20 4:07

What is the difference between area and perimeter?

Re: Area vs perimeter

Dave Kreskowiak11-Aug-20 4:40

Dave Kreskowiak

11-Aug-20 4:40