Better way of writing this List Search


#1

I’m solving the problem of spawning things in a grid while making sure that items never spawn in:

  1. The same grid location
  2. A blacklisted list of grid locations

I’m curious if you might see any more :sk:-umy ways to do the list search.

Here’s a self-contained example that can run on the REPL :warning: running with num nearly equal to 100 will end poorly:

!num : 10
!bad_locations : {Vector2!xy(5, 4) Vector2!xy(5, 5) Vector2!xy(6, 4) Vector2!xy(6, 5)}
!locations : List{Vector2}!

loop
[
  // Random grid coordinate ([1, 10], [1, 10])
  !l : Vector2!xy([@@random.uniform_int(10)>>Real + 1.0],
                  [@@random.uniform_int(10)>>Real + 1.0])

  //>>>>>>> Any better way of writing this?
  if [not locations.find?[item = l]] and [not bad_locations.find?[item = l]]
  [
    locations += {l}
  ]
  [exit] when locations.length = num
]

#2

There are a few minor things that you can do, though what you really want is a few library additions that we have planned.

Without some new library additions (detailed below) it is about as Skookum-y as it can go.

Here are a few small optimizations:

!num : 10
!bad_locations : {Vector2!xy(5, 4) Vector2!xy(5, 5) Vector2!xy(6, 4) Vector2!xy(6, 5)}
//>> Simpler way to specify an empty typed list
!locations : Vector2{}
//>> If you declare a temporary variable outside a loop, it is a tiny bit faster
!l

loop
[
  // Random grid coordinate ([1, 10], [1, 10])
  //>> There is a Real-based @@random.uniform_range(1 10), though it gives fractional values.
  //>> If you want Integer values, best to keep them as an integer for as long as possible
  l : Vector2!xy(
    [@@random.uniform_int(10) + 1]>>Real
    [@@random.uniform_int(10) + 1]>>Real)

  //>> You can combine the two tests and eliminate a not
  if [not [locations.find?[item = l] or bad_locations.find?[item = l]]]
  [
    //>> A simple append() is more efficient than wrapping an item and a list and concatenating it
    locations.append(l)
    //>> Since the location length can only change in this clause, put the exit test here
    [exit] when locations.length = num
  ]
]

If you want to eliminate a list test, you could also append bad_locations to locations while adding new locations and then remove them afterwards.

It might make sense to create some of your own custom data structures. Sometimes knowing some of the constraints of a situation - like the particulars of your grid - can allow you to make something that is simple and efficient.

We have a few planned library additions that also may help you when they are available.

New library additions

What you really want is some additional library classes and routines that are more suitable for what you are trying to do. These don’t exist yet, though they are planned for the near future. Let us know if you need them and we can see about increasing their priority.

More List methods:

If you look at the List class, there are a bunch of routines (about 14) with _same in their name. It indicates that those routines test whether the items are the same - i.e. are they the same object in memory. There is also a same?() routine that can determine this case - obj1.same?(obj2).

Since logical Boolean equals tests (=, ~=) are so common, we can add some routines that use them to do their comparison. Such as: remove(), append_absent(), intersection(), union() and logical versions of all the closure methods too.

These logical routines would be faster than the closure versions.

Sorted - an always sorted version of List:

In a Sorted list, whenever you append an item it is auto-sorted into place. This also means that all search routines are much faster.

Set - a version of List that does not allow duplicates:

Essentially a Sorted that does not allow duplicates.

Based on what you are trying to do above, it sounds like this is probably the best fit. The code would look really similar though it would be much more efficient - especially at scale.


#3

Thanks for the recommendations, I’ve learned some things. If I were to revisit the entire implementation it really would make most sense to use a Set. I could have used the :ue4: TSet type for this which includes the usual set->set operations Intersection, Union, Difference and Includes but then it would have taken me an hour and some C++ instead of 10-minutes in the REPL :madsci:

My quick solution seems to have satisfied the demo requirements. If those requirements stick for more than a week, I’ll go back and make sure this doesn’t touch the shipping product, so I wouldn’t speed the Set implementation just for me.


#4

We see the Set implementation and the rest of what I mentioned above as something we need before we progress from Beta to Release. So its implementation is planned for the near future.