A JDK String.repeat megvalósítása Java 11-ben
A Java 11 óta. Van egy új metódus a String osztályban, az úgynevezett repeat. Igen, gyorsan ismétli a húrt. Most tippelj. Hány megvalósítási sor van benne? Egysoros? Stream-divatos egysoros? 5-7 sor? 9? 12? Több. Sokkal több. Ebben a cikkben azt szeretném megvizsgálni, hogy miért. Kész vagy?
Kezdje profiként
Az első sorokat a bejövő paraméterek ellenőrzésére szánjuk. A civilizálatlan barbárok negatív számot adhatnak. Meg kell védenünk a királyságot, és riasztanunk kell. A nulla hosszúságú bemeneti karakterlánc vagy a no-repeat azt jelenti, hogy nincs munka, ezért pihenjen, és adjon vissza egy üres karakterláncot. Ha az ismétlődések száma eggyel egyenlő, akkor az énre való hivatkozást adjuk vissza. Nem sértjük meg a kódot, mivel a karakterlánc megváltoztathatatlan.
if (count < 0) {
throw new IllegalArgumentException("count is negative: "+count);
}
if (count == 1) {
return this;
}
final int len = value.length;
if (len == 0 || count == 0) {
return "";
}
Teljesítményteljesítmény első számú, egybetűs optimalizálás
Most hozzuk létre a feliratgenerátort. Képzelj el egy jelenetet, ahol emberek zuhannak a lyukba. A furat mélységével arányos hosszúságú „aaaaaaaaaaa”-t kell generálnunk. A terület szakértői azt javasolnák, hogy sokszor fűzzék hozzá ugyanazt a betűt a Stringhez, igaz? Ez helytelen. Ez a tökéletes eset a Array osztályhoz!
if (len == 1) {
final byte[] single = new byte[count];
Arrays.fill(single, value[0]);
return new String(single, coder);
}
Lehet, hogy nem hiszi el, de az Arrays.fill kitölti a tömböt. Micsoda csavar, igaz? Lehet, hogy a belső módszer is bonyolult, de nem az. Valójában ez egy egyszerű hurok. Az előny az, hogy a memória már le van foglalva. Nem kell megrángatnunk a memóriát sok blokk összefűzésével.
for (int i = 0, len = a.length; i < len; i++)
a[i] = val;
Kár. Nem tudunk mutatót visszaadni erre a tömbre, ezért vissza kell konvertálnunk a String-re – a C++-t nézem. Hé, de miért kell itt egy második érv, a kódoló?
new String(single, coder)
A vonós osztály testőrző memória
A memória olcsó, olcsó és gyors. Hacsak nem drága, mert nagy szükségünk van rá. 500 dollárt költeni jobb, mint 1000 dollárt, igaz? Ez az oka a kódolónak. Ha lehetséges, LATIN1 kódolást használunk, így a karakterek csak 8 bájtot fogyasztanak. Ha néhány karakter kívül esik a hatókörön, akkor az UTF16-ra térünk vissza. Megfigyelhetjük egy ismeretlen karakter számítását a String.valueOf metódusban:
public static String valueOf(char c) {
if (COMPACT_STRINGS && StringLatin1.canEncode(c)) {
return new String(StringLatin1.toBytes(c), LATIN1);
}
return new String(StringUTF16.toBytes(c), UTF16);
}
Az ismétlésmódszerben az újraszámítás elkerülése érdekében az eredeti karakterláncból adjuk át az értéket. Ha ismerjük a karaktereket, nem kell ellenőrizni. Nem fogunk új karakterkódokat hozzáadni azok ismétlésével. Nem kell dolgozni!
Nem jutsz át
Ismételten a memória gondozása prioritást élvez az olyan kritikus osztályok esetében, mint a String. A folyamat ismétlése bizonyos esetekben memóriahibákat fog kiadni, függetlenül attól, hogy mi történik. Megjósolhatjuk ezt? Elkerülhetjük-e az időveszteséget az amúgy is sikertelen műveletre? A mágikus labda vagy a tarot előrejelző rendszer működhet itt, de nem pontosak. Ehelyett számok alapján kiszámolhatjuk a várható hosszt.
if (Integer.MAX_VALUE / count < len) {
throw new OutOfMemoryError("Repeating " + len + " bytes String " + count + " times will produce a String exceeding maximum size.");
Az Integer.MAX_VALUE 0x7fffffff, ami ²³¹-1. Ha az előállított String nagyobb lesz, mint ~2 GB, akkor azonnal összeomolhatunk.
Hölgyeim és uraim, várva várt sztárunk
Ismételten a memória gondozása prioritást élvez az olyan kritikus osztályok esetében, mint a String. Egyes esetekben az ismétlési folyamat memóriahibákat produkál, bármitől függetlenül. Megjósolhatjuk ezt? Tehát nem pazaroljuk az időt a műveletre, amely úgyis meghiúsul? A mágikus labda vagy a tarot előrejelző rendszer néha működhet, de nem minden esetben pontos. Ehelyett számok alapján kiszámolhatjuk a várható hosszt.
final int limit = len * count;
final byte[] multiple = new byte[limit];
System.arraycopy(value, 0, multiple, 0, len);
int copied = len;
for (; copied < limit - copied; copied <<= 1) {
System.arraycopy(multiple, 0, multiple, copied, copied);
}
System.arraycopy(multiple, 0, multiple, copied, limit - copied);
return new String(multiple, coder);
Hol található a Stringrepeat tényleges megvalósítása? Mielőtt a tényleges kódra ugrunk, tegyünk egy rövid összefoglalót, mi az a System.arraycopy? Ez az ismétlés kód egyik fő építőköve, ezért tudnunk kell. Ismét van tömbműveletünk. Ezúttal a Array töredékét másoljuk át egyik helyről a másikra.
char[] a = "abcdefghi".toCharArray(); char[] b = "123456789".toCharArray(); System.arraycopy(a, 2, b, 4, 3); System.out.println(a); // abcdefghi System.out.println(b); // 1234cde89
Nézzük meg a System.arraycopy forráskódját. Nem ad sok információt, mivel ez egy Java natív módszer. Ez azt jelenti, hogy a JVM és az operációs rendszer hatékonyan tudja támogatni futás közben.
/**
* Copies an array from the specified source array, beginning at the
* specified position, to the specified position of the destination array.
...
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
...
*/
@HotSpotIntrinsicCandidate
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
A fő kód
Először is helyet csinálunk a kimeneti karakterláncnak:
final int limit = len * count; final byte[] multiple = new byte[limit];
Ezután az eredeti karakterlánc átkerül az új tömbbe (az első előfordulás):
System.arraycopy(value, 0, multiple, 0, len);
Ezután van egy hurok, amely 2 trükköt hajt végre.
int copied = len;
for (; copied < limit - copied; copied <<= 1) {
System.arraycopy(multiple, 0, multiple, copied, copied);
}
Csak a céltömb kerül felhasználásra, és minden ciklus kétszer másol minden iteráció során. Az első ciklus után két előfordulásunk van, majd négy, nyolc, tizenhat stb.
1: copycopy............................ 2: copycopycopycopy.................... 3: copycopycopycopycopycopycopycopy.... 4: ?
Minden iteráció gyorsabb lesz a másolás során, mivel a másolási művelet a nagyobb darabokhoz lesz optimalizálva. Természetesen egy bizonyos ponton nem tudjuk megkettőzni az adatokat, mivel nincs elég hely a tömbben. Az utolsó lépés a fennmaradó hely kitöltése és az eredmény létrehozása:
System.arraycopy(multiple, 0, multiple, copied, limit - copied); return new String(multiple, coder);
A végén megvan az ismétlődő karakterláncunk.
3: copycopycopycopycopycopycopycopy.... 4: copycopycopycopycopycopycopycopycopy
Mielőtt befejeznénk
Nézzük meg a módszer teljes forráskódját.
/**
* Returns a string whose value is the concatenation of this
* string repeated {@code count} times.
* <p>
* If this string is empty or count is zero then the empty
* string is returned.
*
* @param count number of times to repeat
*
* @return A string composed of this string repeated
* {@code count} times or the empty string if this
* string is empty or count is zero
*
* @throws IllegalArgumentException if the {@code count} is
* negative.
*
* @since 11
*/
public String repeat(int count) {
if (count < 0) {
throw new IllegalArgumentException("count is negative: " + count);
}
if (count == 1) {
return this;
}
final int len = value.length;
if (len == 0 || count == 0) {
return "";
}
if (len == 1) {
final byte[] single = new byte[count];
Arrays.fill(single, value[0]);
return new String(single, coder);
}
if (Integer.MAX_VALUE / count < len) {
throw new OutOfMemoryError("Repeating " + len + " bytes String " + count +
" times will produce a String exceeding maximum size.");
}
final int limit = len * count;
final byte[] multiple = new byte[limit];
System.arraycopy(value, 0, multiple, 0, len);
int copied = len;
for (; copied < limit - copied; copied <<= 1) {
System.arraycopy(multiple, 0, multiple, copied, copied);
}
System.arraycopy(multiple, 0, multiple, copied, limit - copied);
return new String(multiple, coder);
}
Ne csináld ezt otthon!
Egy átlagos rendszerben ilyen kódot írni olyan, mintha egy F1-es autóval hajtanák a gyerekeket iskolába – indokolatlan őrület. De a JDK fejlesztői szemszögéből ez más. A kód segítségével ténylegesen megépíthetjük az F1-es autó egyes részeit.
