Полный набор setdiff для двух числовых векторов с числовым порогом для принятия совпадений
Я разработал решение, которое выглядит легче, чем то, что было опубликовано здесь
private String executeGet(final String https_url, final String proxyName, final int port) {
String ret = "";
URL url;
try {
HttpsURLConnection con;
url = new URL(https_url);
if (proxyName.isEmpty()) {
con = (HttpsURLConnection) url.openConnection();
} else {
Proxy proxy = new Proxy(Proxy.Type.HTTP, new InetSocketAddress(proxyName, port));
con = (HttpsURLConnection) url.openConnection(proxy);
Authenticator authenticator = new Authenticator() {
public PasswordAuthentication getPasswordAuthentication() {
return (new PasswordAuthentication(USERNAME, PASSWORD.toCharArray()));
}
};
Authenticator.setDefault(authenticator);
}
ret = getContent(con);
} catch (MalformedURLException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return ret;
}
3 ответа
Если вы счастливы использовать пакет не base, data.table::inrange является удобной функцией.
x1[!inrange(x1, x2 - 0.045, x2 + 0.045)]
# [1] 1002.570 301.569
x2[!inrange(x2, x1 - 0.045, x1 + 0.045)]
# [1] 22.12 53.00 5666.31 100.10
inrange также эффективен для больших наборов данных. Напр. 1e5, inrange в > 700 раз быстрее, чем две другие альтернативы:
n <- 1e5
b1 <- runif(n, 0, 10000)
b2 <- b1 + runif(n, -1, 1)
microbenchmark(
f1 = f(b1, b2, 0.045, 5000),
f2 = list(in_b1_not_in_b2 = b1[sapply(b1, function(x) !any(abs(x - b2) <= 0.045))],
in_b2_not_in_b1 = b2[sapply(b2, function(x) !any(abs(x - b1) <= 0.045))]),
f3 = list(in_b1_not_in_b2 = b1[!inrange(b1, b2 - 0.045, b2 + 0.045)],
in_b2_not_in_b1 = b2[!inrange(b2, b1 - 0.045, b1 + 0.045)]),
unit = "relative", times = 10)
# Unit: relative
# expr min lq mean median uq max neval
# f1 1976.931 1481.324 1269.393 1103.567 1173.3017 1060.2435 10
# f2 1347.114 1027.682 858.908 766.773 754.7606 700.0702 10
# f3 1.000 1.000 1.000 1.000 1.0000 1.0000 10
И да, они дают тот же результат:
n <- 100
b1 <- runif(n, 0, 10000)
b2 <- b1 + runif(n, -1, 1)
all.equal(f(b1, b2, 0.045, 5000),
list(in_b1_not_in_b2 = b1[sapply(b1, function(x) !any(abs(x - b2) <= 0.045))],
in_b2_not_in_b1 = b2[sapply(b2, function(x) !any(abs(x - b1) <= 0.045))]))
# TRUE
all.equal(f(b1, b2, 0.045, 5000),
list(in_b1_not_in_b2 = b1[!inrange(b1, b2 - 0.045, b2 + 0.045)],
in_b2_not_in_b1 = b2[!inrange(b2, b1 - 0.045, b1 + 0.045)]))
# TRUE
Несколько связанных, потенциально полезных ответов, когда ищет inrange на SO .
Вот альтернативный подход
in_b1_not_in_b2 <- b_1[sapply(b_1, function(x) !any(abs(x - b_2) <= 0.045))]
in_b1_not_in_b2
#[1] 1002.570 301.569
in_b2_not_in_b1 <- b_2[sapply(b_2, function(x) !any(abs(x - b_1) <= 0.045))]
in_b2_not_in_b1
#[1] 22.12 53.00 5666.31 100.10
Векторизованный зверь:
D <- abs(outer(b_1, b_2, "-")) > 0.045
in_b1_not_in_b2 <- b_1[rowSums(D) == length(b_2)]
#[1] 1002.570 301.569
in_b2_not_in_b1 <- b_2[colSums(D) == length(b_1)]
#[1] 22.12 53.00 5666.31 100.10
спустя несколько часов ...
Хенрик поделился вопросом, жалуясь на взрыв памяти при использовании outer для длинных векторов: Согласование двух очень очень больших векторов с толерантностью (быстрая, но экономия рабочего пространства) . Однако узкое место памяти для outer можно легко убить путем блокировки.
f <- function (b1, b2, threshold, chunk.size = 5000) {
n1 <- length(b1)
n2 <- length(b2)
chunk.size <- min(chunk.size, n1, n2)
RS <- numeric(n1) ## rowSums, to be accumulated
CS <- numeric(n2) ## colSums, to be accumulated
j <- 0
while (j < n2) {
chunk.size_j <- min(chunk.size, n2 - j)
ind_j <- (j + 1):(j + chunk.size_j)
b2_j <- b2[ind_j]
i <- 0
while (i < n1) {
chunk.size_i <- min(chunk.size, n1 - i)
ind_i <- (i + 1):(i + chunk.size_i)
M <- abs(outer(b1[ind_i], b2_j, "-")) > threshold
RS[ind_i] <- RS[ind_i] + rowSums(M)
CS[ind_j] <- CS[ind_j] + colSums(M)
i <- i + chunk.size_i
}
j <- j + chunk.size_j
}
list(in_b1_not_in_b2 = b1[RS == n2], in_b2_not_in_b1 = b2[CS == n1])
}
С помощью этой функции outer никогда не использует больше памяти, чем сохранение двух chunk.size x chunk.size матриц. Теперь давайте сделаем что-то безумное.
b1 <- runif(1e+5, 0, 10000)
b2 <- b1 + runif(1e+5, -1, 1)
Если мы сделаем простую outer, нам понадобится память для хранения двух 1e+5 x 1e+5 матриц, что составляет до 149 ГБ. Тем не менее, на моем ноутбуке Sandy Bridge (2011) с 4 ГБ оперативной памяти возможно вычисление.
system.time(oo <- f(b1, b2, 0.045, 5000))
# user system elapsed
#365.800 167.348 533.912
Производительность на самом деле достаточно хороша, учитывая, что мы использовали очень плохой алгоритм.
Все ответы здесь исчерпывают поиск, который имеет сложность length(b1) x length(b2). Мы могли бы уменьшить это до length(b1) + length(b2), если мы будем работать с отсортированными массивами. Но такой оптимизированный алгоритм может быть реализован только с использованием компилируемого языка для повышения эффективности.