From Strings to Lists...and Back Again

November 9, 2001
by Dan Manes

Have you ever noticed that Director moves like a snail on NyQuil when working with strings and more like a cheetah with a caffeine buzz when you use lists instead? If you have, then you may have actually converted some of your longer strings into lists. Aside from some major improvements in speed, you probably noticed a plethora of other benefits, such as better organization, automatic sorting, and rapid searches.

"BUT!", you might be thinking, "The last time I tried to convert a long string to a list, my computer came to a screeching halt." Which shouldn't be surprising since Director has to do a whole mess of operations on that long string to make that conversion -- at least if you're doing things the old way. Yes, the old way. You repeat through each item in the string, appending one item at a time to a list. What could be simpler?

What could be slower?

If you think about what Director has to do, you will see why it gets so bogged down. Director finds items (or words or lines) in strings by literally searching through the characters one-by-one until it finds that magic one called the itemDelimiter. At this point, it says:"Okay, that's the end of the first item." If you're searching for item number 1000, it says:"Only 999 more to go." Kinda' reminds you of that old "100 Bottles of Beer on the Wall" song, doesn't it? If you have a long string, and you tell Director to grab every item one-by-one, it will take longer and longer the higher the item number (and no, Director is not smart enough to pick up where it left off-it starts from the beginning of the string each and every time it goes to look for something).

So, you've probably had it up to here with the old way and are good and ready to hear about the new way. The new way is basically to break up those long strings into halves. And break those halves into quarters. And break those quarters into eighths. You keep going until each string is just one item long. Pretty neat, huh? And as you will see shortly, not terribly difficult to code. By the way, the resemblance of this to that famous Binary Search Algorithm is no accident. The new way is, in fact, the binary way.

At this point, you may be wondering if there is a binary technique for getting a long list of items back into a string again. The answer is, of course! You pretty much just have to reverse the process by pairing consecutive items. In other words, you go through your list of items and combine each pair of items into twins. Then you combine each pair of twins into quadruplets. As the process continues, you end up with octuplets and big conglomerations I don't even know the word for. Anyway, in the end, what you have is a single really long string.

So, without further adieu, here is the Lingo that does these conversions. Notice I have provided handlers for both the old (serial) way (serialStringToList and serialListToString) and the new (binary) way (binaryStringToList and binaryListToString).

on serialStringToList InputString, ItemDelim

  OrigDelim = the itemDelimiter
  the itemDelimiter = ItemDelim
  OutputList = []
  TotalItems = InputString.item.count
  repeat with ItemIndex = 1 to TotalItems
    ItemString = InputString.item[ItemIndex]
    OutputList.append (ItemString)
  end repeat
  the itemDelimiter = OrigDelim
  return OutputList

end

on serialListToString InputList, ItemDelim

  OrigDelim = the itemDelimiter
  the itemDelimiter = ItemDelim
  OutputString = EMPTY
  repeat with ItemIndex = 1 to InputList.count
    ItemString = InputList[ItemIndex]
    OutputString = OutputString &ItemDelim &ItemString
  end repeat
  delete OutputString.item[1]
  the itemDelimiter = OrigDelim
  return OutputString

end

on binaryStringToList InputString, ItemDelim -- keep cutting strings in half until there is only one item per string

  OrigDelim = the itemDelimiter
  the itemDelimiter = ItemDelim
  TotalItems = InputString.item.count
  MainItemsList = list (TotalItems) -- keep track of the total items of each string
  MainList = list (InputString)
  repeat while MainList.count < TotalItems
    TempItemsList = []
    TempList = []
    repeat with MainIndex = 1 to MainList.count
      MainItems = MainItemsList[MainIndex]
      HalfwayPoint = MainItems / 2
      MainString = MainList[MainIndex]
      if MainItems > 1 then
        TempItemsList.append (HalfwayPoint)
        TempList.append (MainString.item[1..HalfwayPoint])
      end if
      TempItemsList.append (MainItems - HalfwayPoint)
      TempList.append (MainString.item[HalfwayPoint + 1..MainItems])
    end repeat
    MainItemsList = TempItemsList
    MainList = TempList -- the MainList now contains double the strings, but each string contains half the items
  end repeat
  the itemDelimiter = OrigDelim
  return MainList

end

on binaryListToString InputList, ItemDelim -- keep pairing adjacent strings together until only a single string remains

  MainList = InputList
  repeat while MainList.count > 1
    TempList = []
    repeat with MainIndex = 1 to MainList.count
      MainIndex = MainIndex + 1 -- skip to the next index so that the index steps by two
      FirstString = MainList[MainIndex - 1] -- grab the first string in the pair
      if MainIndex > MainList.count then MergeString = FirstString
      else
        SecondString = MainList[MainIndex] -- grab the second string in the pair
        MergeString = FirstString &ItemDelim &SecondString -- merge the two strings together
      end if
      TempList.append (MergeString)
    end repeat
    MainList = TempList -- the MainList now contains half the strings, but each string contains double the items
  end repeat
  if MainList.count = 0 then OutputString = EMPTY
  else OutputString = MainList[1]
  return OutputString

end

Now for the fun part. To actually see for yourself just how staggering the difference is between serial and binary, paste the above handlers as well as the "compareTimes" handler below into a movie script (or download the convenient Director 7-compatible test movie in Mac or Windows format).

on compareTimes ItemDelim
BaseString = member ("Test Data").text

  BeginTime = the milliseconds -- test serialStringToList
  TestList = serialStringToList (BaseString, ItemDelim)
  NetTime = the milliseconds - BeginTime
  put "serialStringToList: " &NetTime

  BeginTime = the milliseconds -- test serialListToString
  TestString = serialListToString (TestList, ItemDelim)
  NetTime = the milliseconds - BeginTime
  put "serialListToString: " &NetTime

  BeginTime = the milliseconds -- test binaryStringToList
  TestList = binaryStringToList (BaseString, ItemDelim)
  NetTime = the milliseconds - BeginTime
  put "binaryStringToList: " &NetTime

  BeginTime = the milliseconds -- test binaryListToString
  TestString = binaryListToString (TestList, ItemDelim)
  NetTime = the milliseconds - BeginTime
  put "binaryListToString: " &NetTime
end

Stick a new field into your cast called "Test Data" and paste in a long string with lots of items. "Items" can be anything you want-words, lines, comma- or tab-delimited lists, etc.

To test the speed, type compareTimes SPACE or compareTimes RETURN in the message window (depending on which character you want to use for an item delimiter).

[Editor's note: With 400 lines of data, the test movie we're providing can take upward of 20 seconds to run all four tests, you can cut that down by reducing the amount of text in the Test Data field.]

-- Welcome to Director --
comparetimes space
-- "serialStringToList: 16567"
-- "serialListToString: 1263"
-- "binaryStringToList: 578"
-- "binaryListToString: 371"

Sample output from the test movie on a MacOS G4/400 in Director 7.

If your test string is long enough, you should note that the binary technique takes considerably less time. So, if you like your code to run like your trutsy old minivan, then by all means, use the serial handlers. For a more Ferrari-like experience, go with the binary.

Daniel Manes is an engineer at Pacific Science & Engineering Group, Inc., a company specializing in human factors research and development. In the past four years, he has used Macromedia Director extensively in the production of demonstrations, prototype user interfaces, and data collection software for both the military and private sector.