summaryrefslogtreecommitdiffstats
path: root/facebook_analysis/ads.pyx
diff options
context:
space:
mode:
Diffstat (limited to 'facebook_analysis/ads.pyx')
-rw-r--r--facebook_analysis/ads.pyx403
1 files changed, 403 insertions, 0 deletions
diff --git a/facebook_analysis/ads.pyx b/facebook_analysis/ads.pyx
new file mode 100644
index 0000000..2682456
--- /dev/null
+++ b/facebook_analysis/ads.pyx
@@ -0,0 +1,403 @@
+#!python
+#cython: boundscheck=False, nonecheck=False
+cimport cython
+import random
+
+
+@cython.nonecheck(False)
+cdef int merge_opt(list l1, list l2, int t, dict degrees):
+ cdef int n1, n2, i, j, n, s
+ n1 = len(l1)
+ n2 = len(l2)
+ i = j = n = s = 0
+ while n < t:
+ if i == n1 and j == n2:
+ break
+ if i == n1:
+ s += degrees[l2[j]]
+ j += 1
+ n += 1
+ continue
+ if j == n2:
+ s += degrees[l1[i]]
+ i += 1
+ n += 1
+ continue
+
+ li, lj = l1[i], l2[j]
+ di, dj = degrees[li], degrees[lj]
+ if lj == li:
+ j += 1
+ s += di
+ i += 1
+ n += 1
+ elif di > dj:
+ s += di
+ i += 1
+ n += 1
+ else:
+ s += dj
+ j += 1
+ n += 1
+ return s
+
+@cython.nonecheck(False)
+cdef float merge_opt_p(list l1, list l2, int t, dict degrees, float p):
+ cdef int n1, n2, i, j
+ cdef float n, s
+ n1 = len(l1)
+ n2 = len(l2)
+ i = j = 0
+ n = s = 0.
+ while n < t:
+ if i == n1 and j == n2:
+ break
+ if i == n1:
+ s += degrees[l2[j]]*p
+ j += 1
+ n += p
+ continue
+ if j == n2:
+ s += degrees[l1[i]]*p
+ i += 1
+ n += p
+ continue
+
+ li, lj = l1[i], l2[j]
+ di, dj = degrees[li], degrees[lj]
+ if lj == li:
+ j += 1
+ s += di*p
+ i += 1
+ n += p
+ elif di > dj:
+ s += di*p
+ i += 1
+ n += p
+ else:
+ s += dj*p
+ j += 1
+ n += p
+ return s
+
+
+@cython.nonecheck(False)
+cdef float merge_opt_p_sample(list l1, list l2, int t, dict degrees, float p):
+ random.seed()
+ cdef int n1, n2, i, j
+ cdef float n, s
+ n1 = len(l1)
+ n2 = len(l2)
+ i = j = 0
+ n = s = 0.
+ cdef int k
+ cdef dict a
+ cdef float r
+ k = 0
+ r = 0
+ a = {}
+ for k in xrange(len(degrees)**2):
+ for d in degrees:
+ a[d] = random.random()
+ while n < t:
+ if i == n1 and j == n2:
+ break
+ if i == n1:
+ s += degrees[l2[j]]*p
+ j += 1
+ n += p
+ continue
+ if j == n2:
+ s += degrees[l1[i]]*p
+ i += 1
+ n += p
+ continue
+
+ li, lj = l1[i], l2[j]
+ di, dj = degrees[li], degrees[lj]
+ if lj == li:
+ j += 1
+ s += di*p
+ i += 1
+ n += p
+ elif di > dj:
+ s += di*p
+ i += 1
+ n += p
+ else:
+ s += dj*p
+ j += 1
+ n += p
+ r += s
+ r /= n**2
+ return r
+
+
+@cython.nonecheck(False)
+cdef float merge_opt_ps(list l1, list l2, int t, dict degrees, dict p):
+ cdef int n1, n2, i, j
+ cdef float n, s
+ n1 = len(l1)
+ n2 = len(l2)
+ i = j = 0
+ n = s = 0.
+ while n < t:
+ if i == n1 and j == n2:
+ break
+ if i == n1:
+ s += degrees[l2[j]]*p[l2[j]]
+ n += p[l2[j]]
+ j += 1
+ continue
+ if j == n2:
+ s += degrees[l1[i]]*p[l1[i]]
+ n += p[l1[i]]
+ i += 1
+ continue
+
+ li, lj = l1[i], l2[j]
+ di, dj = degrees[li], degrees[lj]
+ if lj == li:
+ j += 1
+ s += di*p[li]
+ n += p[li]
+ i += 1
+ elif di > dj:
+ s += di*p[li]
+ n += p[li]
+ i += 1
+ else:
+ s += dj*p[lj]
+ n += p[lj]
+ j += 1
+ return s
+
+
+@cython.nonecheck(False)
+cdef list merge(list l1, list l2, int t, dict degrees):
+ cdef int n1, n2, i, j, n
+ n1 = len(l1)
+ n2 = len(l2)
+ result = []
+ i = j = n = 0
+ while n < t:
+ if i == n1 and j == n2:
+ break
+ if i == n1:
+ result.append(l2[j])
+ j += 1
+ n += 1
+ continue
+ if j == n2:
+ result.append(l1[i])
+ i += 1
+ n += 1
+ continue
+
+ if l2[j] == l1[i]:
+ j += 1
+ result.append(l1[i])
+ i += 1
+ n += 1
+ elif degrees[l1[i]] > degrees[l2[j]]:
+ result.append(l1[i])
+ i += 1
+ n += 1
+ else:
+ result.append(l2[j])
+ j += 1
+ n += 1
+ return result
+
+@cython.nonecheck(False)
+cdef list merge_p(list l1, list l2, int t, dict degrees, float p):
+ cdef int n1, n2, i, j
+ cdef float n
+ n1 = len(l1)
+ n2 = len(l2)
+ result = []
+ i = j = 0
+ n = 0.
+ while n < t:
+ if i == n1 and j == n2:
+ break
+ if i == n1:
+ result.append(l2[j])
+ j += 1
+ n += p
+ continue
+ if j == n2:
+ result.append(l1[i])
+ i += 1
+ n += p
+ continue
+
+ if l2[j] == l1[i]:
+ j += 1
+ result.append(l1[i])
+ i += 1
+ n += p
+ elif degrees[l1[i]] > degrees[l2[j]]:
+ result.append(l1[i])
+ i += 1
+ n += p
+ else:
+ result.append(l2[j])
+ j += 1
+ n += p
+ return result
+
+
+@cython.nonecheck(False)
+cdef list merge_ps(list l1, list l2, int t, dict degrees, dict p):
+ cdef int n1, n2, i, j
+ cdef float n
+ n1 = len(l1)
+ n2 = len(l2)
+ result = []
+ i = j = 0
+ n = 0.
+ while n < t:
+ if i == n1 and j == n2:
+ break
+ if i == n1:
+ result.append(l2[j])
+ n += p[l2[j]]
+ j += 1
+ continue
+ if j == n2:
+ result.append(l1[i])
+ n += p[l1[i]]
+ i += 1
+ continue
+
+ if l2[j] == l1[i]:
+ j += 1
+ result.append(l1[i])
+ n += p[l1[i]]
+ i += 1
+ elif degrees[l1[i]] > degrees[l2[j]]:
+ result.append(l1[i])
+ n += p[l1[i]]
+ i += 1
+ else:
+ result.append(l2[j])
+ n += p[l2[j]]
+ j += 1
+ return result
+
+@cython.nonecheck(False)
+def fs(tuple a):
+ cdef int cur_val, best_diff, best_value, o, t, k
+ cdef list x
+ cdef dict graph
+ cdef dict degrees
+ t, k, x, graph, degrees = a
+ cdef list n
+ cur_val = 0
+ n = [] # neighbors of greedy set
+ for i in range(1, k - t):
+ best_diff = 0
+ best_user = None
+ best_value = 0
+ for user in x:
+ o = merge_opt(n, graph[user], t, degrees)
+ if o - cur_val > best_diff:
+ best_diff = o - cur_val
+ best_user = user
+ best_value = o
+ if best_user is not None:
+ x.remove(best_user)
+ cur_val = best_value
+ n = merge(n, graph[best_user], t, degrees)
+ else:
+ break
+ return cur_val
+
+@cython.nonecheck(False)
+def fs_p(tuple a):
+ cdef int t, k
+ cdef float o, p, best_value, best_diff, cur_val
+ cdef list x
+ cdef dict graph
+ cdef dict degrees
+ t, k, x, graph, degrees, p = a
+ cdef list n
+ cur_val = 0
+ n = [] # neighbors of greedy set
+ for i in range(1, k - t):
+ best_diff = 0
+ best_user = None
+ best_value = 0
+ for user in x:
+ o = merge_opt_p(n, graph[user], t, degrees, p)
+ if o - cur_val > best_diff:
+ best_diff = o - cur_val
+ best_user = user
+ best_value = o
+ if best_user is not None:
+ x.remove(best_user)
+ cur_val = best_value
+ n = merge_p(n, graph[best_user], t, degrees, p)
+ else:
+ break
+ return cur_val
+
+@cython.nonecheck(False)
+def fs_p_sample(tuple a):
+ cdef int t, k
+ cdef float o, p, best_value, best_diff, cur_val
+ cdef list x
+ cdef dict graph
+ cdef dict degrees
+ t, k, x, graph, degrees, p = a
+ cdef list n
+ cur_val = 0
+ n = [] # neighbors of greedy set
+ for i in range(1, k - t):
+ best_diff = 0
+ best_user = None
+ best_value = 0
+ for user in x:
+ o = merge_opt_p_sample(n, graph[user], t, degrees, p)
+ if o - cur_val > best_diff:
+ best_diff = o - cur_val
+ best_user = user
+ best_value = o
+ if best_user is not None:
+ x.remove(best_user)
+ cur_val = best_value
+ n = merge_p(n, graph[best_user], t, degrees, p)
+ else:
+ break
+ return cur_val
+
+@cython.nonecheck(False)
+def fs_ps(tuple a):
+ cdef int t, k
+ cdef float o, best_value, best_diff, cur_val
+ cdef list x
+ cdef dict graph
+ cdef dict degrees
+ cdef dict p
+ t, k, x, graph, degrees, p = a
+ cdef list n
+ cur_val = 0
+ n = [] # neighbors of greedy set
+ for i in range(1, k - t):
+ best_diff = 0
+ best_user = None
+ best_value = 0
+ for user in x:
+ o = merge_opt_ps(n, graph[user], t, degrees, p)
+ if o - cur_val > best_diff:
+ best_diff = o - cur_val
+ best_user = user
+ best_value = o
+ if best_user is not None:
+ x.remove(best_user)
+ cur_val = best_value
+ n = merge_ps(n, graph[best_user], t, degrees, p)
+ else:
+ break
+ return cur_val
generated by cgit v1.2.3-70-g09d2 (git 2.52.0) at 2025-12-21 14:46:09 +0000