Speicher- / Zeitnutzung für den Teilstring-Suchcode
Ich habe eine Teilstringsuche implementiert, die wie erwartet funktioniert und die richtige Ausgabe liefert. In einigen Randfällen wird entweder das Speicher- oder das Zeitlimit überschritten, weil:
- Die Saitenlänge ist zu groß
- Es gibt zu viele Abfragen
Der Code fordert einige Eingaben an:
- ein Faden
- die Anzahl der Abfragen
- Abfrage
Infos zum String und den Abfragen:
- Die Zeichenfolgenlänge ist nicht größer als 300.000 und besteht aus englischen Kleinbuchstaben.
- Die maximale Anzahl von Abfragen beträgt 300.000
- Die Summe der Abfragelängen ist nicht größer als 300.000
Ich bekomme MLE, wenn ich HashMap-Caching verwende, und ich bekomme TLE ohne es.
Wo kann mein Code verbessert werden, damit er auch diese Randfälle behandelt?
use std::collections::HashMap;
use std::io::{stdin, stdout, BufWriter, Write};
fn main() {
let out = &mut BufWriter::new(stdout());
let mut s = String::new();
stdin().read_line(&mut s).expect("Failed to read input");
let s = s.trim();
let mut q = String::new();
stdin()
.read_line(&mut q)
.expect("Failed to read number of queries");
let q: u32 = q.trim().parse().unwrap();
if q == 0 {
writeln!(out, "No").ok();
}
let sorted_suffixes = suffix_array(&s);
let mut saved_idx = HashMap::with_capacity(q as usize);
let mut saved_results = HashMap::with_capacity(q as usize);
for idx in 0..q {
let mut i = String::new();
stdin()
.read_line(&mut i)
.unwrap_or_else(|_| panic!("Failed to read input {}", idx));
let i = i.trim();
let result = saved_results.entry(i.to_string()).or_insert_with(|| {
let sorted_suffixes = saved_idx
.entry(i.len())
.or_insert_with(|| transform(&sorted_suffixes, s, i.len()));
match sorted_suffixes.binary_search(&i) {
Ok(_) => "Yes",
_ => "No",
}
});
writeln!(out, "{}", result).ok();
}
}
fn transform<'a>(prep: &[usize], s: &'a str, max_len: usize) -> Vec<&'a str> {
let str_len = s.len();
let mut result = Vec::with_capacity(prep.len());
for &p in prep {
if p + max_len > str_len {
result.push(&s[p..])
} else {
result.push(&s[p..p + max_len])
}
}
result
}
fn suffix_array(s: &str) -> Vec<usize> {
let s = format!("{}{}", s, "$");
let str_len = s.len();
let (mut prep, mut class) = (vec![0; str_len], vec![0; str_len]);
let mut arr: Vec<(char, usize)> = Vec::with_capacity(str_len);
for (idx, ch) in s.chars().enumerate() {
arr.push((ch, idx));
}
arr.sort_by(|a, b| a.0.cmp(&b.0));
for (idx, a) in arr.iter().enumerate() {
prep[idx] = a.1;
}
for (idx, _) in s.chars().enumerate().skip(1) {
if arr[idx].0 == arr[idx - 1].0 {
class[prep[idx]] = class[prep[idx - 1]];
} else {
class[prep[idx]] = class[prep[idx - 1]] + 1;
}
}
let mut k = 0;
while (1 << k) < str_len {
prep = prep
.iter()
.map(|p| (p + str_len - (1 << k)) % str_len)
.collect();
count_sort(&mut prep, &class);
let mut c_new = vec![0; str_len];
for idx in 1..str_len {
let prev = (
class[prep[idx - 1]],
class[(prep[idx - 1] + (1 << k)) % str_len],
);
let cur = (class[prep[idx]], class[(prep[idx] + (1 << k)) % str_len]);
if cur == prev {
c_new[prep[idx]] = c_new[prep[idx - 1]];
} else {
c_new[prep[idx]] = c_new[prep[idx - 1]] + 1;
}
}
class = c_new;
k += 1;
}
prep
}
fn count_sort(p: &mut Vec<usize>, c: &[i32]) {
let n = &p.len();
let mut cnt = vec![0; *n];
for idx in 0..c.len() {
cnt[c[idx] as usize] += 1;
}
let mut p_new = vec![0; *n];
let mut pos = vec![0; *n];
for idx in 1..*n {
pos[idx] = pos[idx - 1] + cnt[idx - 1];
}
p.iter().for_each(|&item| {
let i = c[item] as usize;
p_new[pos[i]] = item;
pos[i] += 1;
});
*p = p_new;
}
Antworten
Suffix_array
Das erste große Problem, das ich beim Überprüfen des Codes festgestellt habe, war dieser Zyklus
let mut k = 0;
while (1 << k) < str_len {
prep = prep
.iter()
.map(|p| (p + str_len - (1 << k)) % str_len)
.collect(); // what exactly should've happened here
count_sort(&mut prep, &class); // nvm just sort it back
let mut c_new = vec![0; str_len];
for idx in 1..str_len {
let prev = (
class[prep[idx - 1]],
class[(prep[idx - 1] + (1 << k)) % str_len],
);
let cur = (class[prep[idx]], class[(prep[idx] + (1 << k)) % str_len]);
if cur == prev {
c_new[prep[idx]] = c_new[prep[idx - 1]];
} else {
c_new[prep[idx]] = c_new[prep[idx - 1]] + 1;
}
}
class = c_new;
k += 1;
}
es tut etwas prep, als count_sortes anzurufen, und bringt dann die Klasse durcheinander. Nach der zweiten Iteration prepändert sich anscheinend überhaupt nicht so gut wie die Klasse, sodass im Grunde Zeit damit verschwendet wird, count_sortSpeicherpuffer bis zu 300.000 Mal aufzurufen und zuzuweisen / freizugeben. Es ist leicht mit einem einzigen Anruf von austauschbar count_sort.
zweites kleines Problem - for (idx, _) in s.chars().enumerate().skip(1) es ist wirklich eine komplizierte Art zu sagen for idx in 1..str_len. Der Compiler wird wahrscheinlich nicht verwendete Dinge optimieren, aber es ist immer noch eine mögliche Verlangsamung.
Ebenfalls
let (mut prep, mut class) = (vec![0; str_len], vec![0; str_len]);
ist schwerer zu lesen und macht wirklich keinen Sinn, das gerade erstellte Tupel zu lösen. Es ist also besser, sie zu trennen und zu erstellen, Vec<usize>da der Algorithmus keine negativen Werte enthält.
let mut prep = vec![0usize; str_len];
let mut class = vec![0usize; str_len];
Außerdem muss der count_sortzweite Parametertyp korrigiert und unnötige Umwandlung entfernt werden as usize.
count_sort
Ich bin mir nicht sicher, warum Sie sich für neinen Zeiger entschieden haben. Er hilft nirgendwo wirklich und wirkt sich auch nicht auf die Leistung aus. könnte eine gute Idee sein, die Funktion von zu ändern
fn count_sort(p: &mut Vec<usize>, class: &[usize])
zu
fn count_sort(p: Vec<usize>, class: &[usize]) -> Vec<usize>
weil die Funktion ohnehin vorherige Werte verwirft. Wahrscheinlich hilft es dem Compiler, einige Anrufe zu optimieren und das Lesen zu vereinfachen.