In der Doku gibts noch $Collator->getSortKey($string). Vielleicht ist es hilfreich, das zu nutzen? Das würdest du bei N zu vergleichenden Strings also nur genau N mal aufrufen. Vielleicht hilft das?