0

Or ways to get better run time than a nested loop?

How would you design this?

I hope this is the place to ask semi-vague software engineering questions.

My simple simulation is like this:

There is a population of X number of people. Every day, people go to work, which creates some quantity of something. After work, they go and buy some random thing that they want or need that someone else made.

What I have tried:

In my first prototype, the population was a list of People. Each person had methods: work() and buy() In the buy() method, the Person loops through each item on the market, breaking out of the loop as soon as it found what it needed.

The problem is that every day the market gets larger and larger, so looping through it gets longer and longer. Since the simulation is looping through every person, and then through every item, this can get very slow.

In my second prototype, I tried to use a database. Here is a vague sketch of it.

enter image description here

I haven't been able to write code that avoids looping, so it is still slowing down rapidly.

What approaches would yield good results?

I am not sure how to avoid the nested loop of population and market.

How would you design this so it runs smoothly even as the population and market gets larger?

Edits:

What people buy is a set of random things, plus, food, clothing and housing. These don't change, so they search the market for them when they don't have them in their inventory. So I still have to search for specific things, even though they are randomly generated for each person. There are also needs that everyone has.

Things depreciate over time, so the market stabilizes eventually, but certain conditions affect this stabilization. For example, if people cannot take on debt, the market grows much faster than it would if people can borrow to buy things.

The goal of the simulation is an educational game about currency. A certain level of realism is desirable, but not the primary goal.

I appreciate the advice so far on this vague question. This will help me when I go back to the drawing board.

5
  • 1
    Rather than looping through all goods you could pick a category by chance, query the first random small number of items and purchase those. This is more real anyway, people only see a small part of the market. Periodically you could set the price of an item as the reciprocal of its availability and play with that too (people would only buy as much as what they have money for). You may want to link price to category. May 19 at 3:29
  • 6
    There are tons of unknowns in this question which can heavily influence solutions. For example: order of magnitude of the number of persons, of the market size. Why does "the market gets larger and larger", are there no rules to restrict unrestricted growth (in reality, no market grows arbitrarily)? What are the exact rules for "buying a thing" - for picking a random thing, for example, there will be no loop required. What are the overall goals of this simulation (without knowing them, we cannot suggest viable alternatives). And so on.
    – Doc Brown
    May 19 at 5:34
  • 2
    ... I am under the impression one has to go back to the drawing board and clarify the goals and requirements first.
    – Doc Brown
    May 19 at 5:37
  • 2
    At its very core, even if preceded by some general code optimization, the ability to work faster and scale will need to be backed by improved (or additional) hardware. This has an inherent financial cost attached. It sounds like this is a personal sandbox project. Are you willing to pay to achieve this? The only other option would be to put an inherent cap on the amount of content you have to process (e.g. population cap, market cap) in order to stay within what you call reasonable boundaries of performance (i.e. time taken to process it) with the hardware that you have available.
    – Flater
    May 19 at 7:54
  • @Doc Brown I included some more rules for buying. The goal of the simulation is an educational game about currency. A certain level of realism is desireable, but not the primary goal. I should implement more rules to stop the market from growing arbitrarily, and as Mosner said, model groups not individuals.
    – Ben Alan
    May 19 at 15:00

3 Answers 3

2

There are a number of ways of handling simulations. I've worked on a grand total of one simulation project, but it did have a lot of lessons to be learned from the process. Properly scaling requires a few things:

  1. The abstraction is good enough (i.e. modeling a real world system by the literal interactions that happen in that system rarely performs well). Be prepared to tweak your model. The answer by Hans-Martin Mosner shows how a change to the abstraction can help tremendously.
  2. Define the thresholds for success. No model can continually scale indefinitely, so it helps to define the saturation point where you need performance to be satisfactory. Also it helps to define satisfactory performance, i.e. transactions/second or some set of metrics you can measure and track.
  3. Not all data is important all the time. If you can control the total number of actors that are operating concurrently at once without breaking the model, you can scale the system further. Hans-Martin Mosner's answer demonstrates how you can extrapolate large group behavior from a subset of the actors.
  4. Identify and resolve hot spots. Remember the thresholds for success? Hot spots such as iterating over items in a list to find them vs using a hash map to quickly find an item can speed your simulation up tremendously. Hot spots are code that is run in quick succession or that contribute the most to performance issues. Doc Brown's answer hints towards these types of problems.
  5. Simplify the model or the algorithm. In some cases, you have to conceptually change specific aspects of what your software is actually doing to hit the numbers you need to. It may not be perfectly correct, but still "good enough" for the purposes of what you are simulating.
  6. Explore concurrency. Not every model can be run in a multi-threaded manner, but when possible it really helps to leverage all the cores in your CPU. There are also more than one way to address concurrency, and on our project the Actor-Model concept helped scale the system better than running a thread per quadrant (the simulation was map based).

Simulations are a hard problem, and the solutions are not one-size fits all. You can find many surprising sources of delays that are outside your code. I cannot stress the importance of defining the limits of the system you need to satisfy because optimization can cause you to go down rabbit trails that are hard to escape. When you are within the stated limits and are hitting the numbers you expect to hit, don't spend any more time optimizing your simulation.

6

If you simulate individual actors and resources, your code will probably have O(n log n) runtime complexity, i.e. to scale for arbitrary growth you'll need to utilize an ever growing amount of CPU time. For economic simulations, it is probably better to model not individual actors but groups with growing sizes, so you just calculate the amount of resources consumed/produced and the change in population as numbers.

If you're interested in observing the behavior of some individual actors in a game you can simulate a small fixed subset individually considering the population sizes and resource availability determined in the numerical simulation.

Alternatively, you may simulate the behavior of a small but statistically significant number of actors (say 50-100) and use the results to extrapolate numbers for a much bigger population. For example, you may simulate a city of 500,000 inhabitants, of which only 50 are truly simulated in detail, and the numbers for the city are determined by multiplying the simulation results by num_inhabitants / num_simulated (plus/minus some random variation).

1

If you have a large set of data (for example, market goods), and several requests to find items in that set, you need a proper data structure for lookup and retrieval.

Databases provide mainly indexes to support fast lookups, and for many kind of queries, this is totally sufficient, even when you have to search through millions of items. You still have to know precisely which kind of queries you expect and choose the indexes accordingly.

But in case this is not sufficient, you may have to roll out your own data structure (or structures) which supports the specific lookup requests of your simulation, and the requirement that the set of items will increase or change over time. But from what you wrote in the question, we can hardly tell you what kind of data structure(s) will meet your needs, or which search algorithm will be "best" for it. There are several excellent books available about data structures and algorithms, and my recommendation is that you study at least one or two of them, and then try to apply that knowledge to your problem.

Note also that in your simulation, your market won't grow beyond a certain size, either restricted by the running time of the simulation, the available memory, or by the simulation rules themselves. You should estimate some realistic limits and design your data structures with those limits in mind.

1
  • Sorry for the lack of information. It is very much an I-don't-know-where-to-start kind of question. Basically, I was asking for ways to get better run time than a nested loop, which can have many different answers depending on the needs of the program. (I know some stuff about Data Structures, but apparently not enough to instinctively know the solution to this.) Some of those books will probably have the information I need to figure out the solution if the database is not sufficient. So thanks!
    – Ben Alan
    May 20 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.