Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 29 30 31 32 33 34 [35] 36 37 38   вперед  Ctrl
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
scf
Member

Откуда:
Сообщений: 1476
Atum1,

volatile boolean cancel = false;
void task() {
  if (cancel) return;
  //do something useful
  if (!cancel) scheduleOnce(this::task, delay);
}
void start() {
  scheduleOnce(this::task);
}

void stop() {
  cancel = true;
}
2 дек 17, 23:04    [21001435]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
scf,

scf
Atum1,

volatile boolean cancel = false;
void task() {
  if (cancel) return;
  //do something useful
  if (!cancel) scheduleOnce(this::task, delay);
}
void start() {
  scheduleOnce(this::task);
}

void stop() {
  cancel = true;
}


Не идея такая = передавать лямду в которой будет task и ламда для проверки нужно ли этот таск выполнять или уже не нужно , каждый раз как наступает его время исполнения в расписании ....

и если задачу уже не нужно исполнять по расписанию - то остановить ее , отменить и выбросить из исполнителя.
4 дек 17, 11:35    [21003605]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
Задача дня :

дано - массив с масками вида :

90 знаков (в каждой маске есть ровно 30 чисел ! - 30 битов =1 , русское лото - в карточке 30 чисел из 90)

нужно разработать оптимальный алгоритм который найдет тройку билетов которые не пересекаются , содержат все биты !

Массив билетов ~1 млн и более.

пример на 6 битах (в каждом по 2 бита)

110000
001100
000011
7 дек 17, 14:58    [21015307]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
Atum1,

 int i,j,k;
 for (i=0;i<a.length-2;i++) {
  for (j=i+1;j<i<a.length-1;j++) {
   if (r=this.joinCorrect(a[i],a[j])) {
     for (k=j+1;k<a.length;k++) {
       if (this.joinComplete(r,a[k])) return new int[]{i,j,k};
     }
   }
  }
 }
 return null;
7 дек 17, 16:05    [21015606]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
scf
Member

Откуда:
Сообщений: 1476
Сергей Арсеньев,

У меня тоже блуждают мысли, что это оптимальный алгоритм и есть. Если исходные данные не рандомные, можно попытаться опереться на это.
7 дек 17, 16:09    [21015621]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
ну понятное дело, long должно хватить, проверка xor==or, полнота xor==or==тридцать_1
7 дек 17, 16:09    [21015625]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
Хотя зачем тут лонг.
7 дек 17, 16:11    [21015634]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
xoor==or, естественно с погашенными неиспользуемыми битами
7 дек 17, 16:12    [21015640]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
(r=this.joinCorrect(a[i],a[j]))Ю=0

соответственно, для корректных возвращаем объединение, для не корректных -1
7 дек 17, 16:17    [21015666]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
Сергей Арсеньев,

90 бит в лонг как бы не влазят ...

баркоды билетов - как бы перемешаны рендомно .

логика в общем такая - выбрали первый билет из 1 млн случайно и далее ищем его пару , второй и третий билет

O(n2) перебор как бы ?!
8 дек 17, 14:23    [21018284]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
scf
Member

Откуда:
Сообщений: 1476
Atum1,

Походу да, O(n^2). Уменьшить время перебора можно только на константу. Например, оптимимизацией хранения и поиска двоичных последовательностей или построением индексов. К примеру, разделение списка на два по значению первого бита позволит примерно удвоить скорость. При наличии памяти, можно сделать списки по первым двум битам и т.п.
8 дек 17, 14:28    [21018317]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
scf
Atum1,

Походу да, O(n^2). Уменьшить время перебора можно только на константу. Например, оптимимизацией хранения и поиска двоичных последовательностей или построением индексов. К примеру, разделение списка на два по значению первого бита позволит примерно удвоить скорость. При наличии памяти, можно сделать списки по первым двум битам и т.п.


спасибо , интересно
9 дек 17, 13:29    [21020479]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
Задача на collect

  
    @Test
    public void testMappingGameId() {

       List<List<String>> list  = new ArrayList<>();
       
       list.add(Arrays.asList("1","2017" , "1000"));
       list.add(Arrays.asList("1","2018" , "3000"));
       list.add(Arrays.asList("2","2018" , "1000"));
       list.add(Arrays.asList("3","2019" , "1000"));
       
       log.info(list);
       
       // Map map = list.stream().collect(Collectors.toMap(x->x.get(0), [s][b]x-> x.get(1)[/b][/s] ,  (oldValue, newValue) -> oldValue
        //        ,LinkedHashMap::new));
       // log.info(map);
    }


как разложить list по ключу ?! x->x.get(0) и парам в

LinkedHashMap<String, LinkedHashMap<String,String>> ?

нужно :

[ 1 = {2017=1000 , 2018= 3000} ,2={2018=1000},3={2019=1000} ]
9 дек 17, 19:20    [21020959]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Usman
Member

Откуда: من ألماتي
Сообщений: 5599
Atum1
нужно :

[ 1 = {2017=1000 , 2018= 3000} ,2={2018=1000},3={2019=1000} ]
Map<String, Map<String, String>> m = 
    Arrays.asList(
        Arrays.asList("1","2017" , "1000"),
        Arrays.asList("1","2018" , "3000"),
        Arrays.asList("2","2018" , "1000"),
        Arrays.asList("3","2019" , "1000"))
            .stream()
            .collect(Collectors.toMap(
                t -> t.get(0), 
                t -> 
                    t.stream()
                        .collect
                            (Collectors.toMap(
                                k -> t.get(1), 
                                v -> t.get(2), 
                                (k, v) -> k, 
                                LinkedHashMap::new)), 
                (k, v) -> {
                    Map<String, String> kk = 
                        (LinkedHashMap<String, String>) k;
                    
                    Map<String, String> vv = 
                        (LinkedHashMap<String, String>) v;
                    
                    kk.putAll(vv);
                    
                    return k;
                })
            );

System.out.println(m);
9 дек 17, 21:13    [21021134]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
Usman
Atum1
нужно :

[ 1 = {2017=1000 , 2018= 3000} ,2={2018=1000},3={2019=1000} ]



+
Map<String, Map<String, String>> m = 
    Arrays.asList(
        Arrays.asList("1","2017" , "1000"),
        Arrays.asList("1","2018" , "3000"),
        Arrays.asList("2","2018" , "1000"),
        Arrays.asList("3","2019" , "1000"))
            .stream()
            .collect(Collectors.toMap(
                t -> t.get(0), 
                t -> 
                    t.stream()
                        .collect
                            (Collectors.toMap(
                                k -> t.get(1), 
                                v -> t.get(2), 
                                (k, v) -> k, 
                                LinkedHashMap::new)), 
                (k, v) -> {
                    Map<String, String> kk = 
                        (LinkedHashMap<String, String>) k;
                    
                    Map<String, String> vv = 
                        (LinkedHashMap<String, String>) v;
                    
                    kk.putAll(vv);
                    
                    return k;
                })
            );

System.out.println(m);


Спасибо ,

делал через внешнюю коллекцию - но это плохое решние :(
   LinkedHashMap<String, LinkedHashMap<String,String>> hashMap = new LinkedHashMap<>();

        Arrays.asList(
        Arrays.asList("1","2017" , "1000"),
        Arrays.asList("1","2018" , "3000"),
        Arrays.asList("2","2018" , "1000"),
        Arrays.asList("3","2019" , "1000"))
            .stream().
               
                forEachOrdered((x) -> {
               

                     hashMap.computeIfAbsent(x.get(0), k -> new LinkedHashMap<>()).put(x.get(1),x.get(2));
                      
                });
11 дек 17, 11:43    [21023524]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9005
Предполагая, что есть достаточно свободной памяти, можно предварительно разбить исходный массив на корзины по битовым маскам: ноль и более старших бит сброшены, затем единичный бит и значение остальных бит - безразлично.
Если какая-то из корзин пуста - решений нет. Иначе - начинаем с корзины с наименьшим числом кандидатов и делаем проверки.
Технически можно сделать и разбиение на месте, но это излишнее усложнение. Как и 90 бит - для начала я бы решал задачу для int/long.
11 дек 17, 12:23    [21023658]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
Basil A. Sidorov
Предполагая, что есть достаточно свободной памяти, можно предварительно разбить исходный массив на корзины по битовым маскам: ноль и более старших бит сброшены, затем единичный бит и значение остальных бит - безразлично.
Если какая-то из корзин пуста - решений нет. Иначе - начинаем с корзины с наименьшим числом кандидатов и делаем проверки.
Технически можно сделать и разбиение на месте, но это излишнее усложнение. Как и 90 бит - для начала я бы решал задачу для int/long.


Интересно .
Спасибо
11 дек 17, 12:48    [21023783]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Usman
Member

Откуда: من ألماتي
Сообщений: 5599
Atum1,

Можно воспользоваться классом BigInteger: поддержка больших чисел + разные битовые операции.
11 дек 17, 13:39    [21023939]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9005
Если ограничиться 27 битами (9-значные восьмеричные числа), то можно сделать полный перебор и удостовериться, что алгоритм работает правильно и находит все решения.
11 дек 17, 13:52    [21024000]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
Atum1
90 бит в лонг как бы не влазят ...

В смысле 30 влазят.
Atum1
логика в общем такая - выбрали первый билет из 1 млн случайно

это чтоб всегда все остальные перебирать? Если выбирать последовательно, то ранее просмотренные пары можно сразу отбрасывать. Что собственно и было показано j=i+1
Atum1
O(n2) перебор как бы ?!

Ну так - полиномиально сложная задача, еслиб экспоненциально, можно было бы сначала подумать.
12 дек 17, 13:17    [21026984]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
Сергей Арсеньев,

Теоретически можно сначала раскидать всех по корзинам по количеству единиц.
И дальше брать только из подходящих корзин.
Но в худшем случае (например все по 10) все одно - полный перебор.
12 дек 17, 13:21    [21027004]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9005
Сергей Арсеньев
Но в худшем случае (например все по 10) все одно - полный перебор.
n^2 больше, чем m*(n/m)^2.
Асимптотическая сложность одинакова, а вот константы - сильно разные.
12 дек 17, 21:18    [21028696]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1834
Добрый вечер .
Задача для Пятницы :

Монету бросают 8 раз. Найти вероятность того, что герб выпадет ровно 3 раза.

(Решение нужно через метод Монте Карло)

тут решение и описание , кому нужно повторить комбинаторику.

https://www.matburo.ru/tvart_sub.php?p=art_moneta

Время :

~ 206 ms

код
+

import java.util.concurrent.ThreadLocalRandom;
public class Coin {

    public static final int NUMBER = 100_000_000;
    public static final int count = 3;

    public static int runner() {

        int res = ThreadLocalRandom
                .current()
                .ints()
                .limit(NUMBER / 4)
                .reduce(0, (left, right) -> left + sumBitsCounter(right));
        return res;
    }

    public static int sumBitsCounter(int i) {
        int d = Integer.bitCount(i & 0xff000000) == count ? 1 : 0;
        int c = Integer.bitCount(i & 0xff0000) == count ? 1 : 0;
        int b = Integer.bitCount(i & 0xff00) == count ? 1 : 0;
        int a = Integer.bitCount(i & 0xff) == count ? 1 : 0;
        return a + b + c + d;

    }
}



jmh :
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

@Warmup(iterations = 3)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
@Fork(2)
public class CoinTest {
    
    @Benchmark
    public Integer test() {
        int res = Coin.runner();
        return res;
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(CoinTest.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }
    
    
}


# JMH 1.12 (released 630 days ago, please consider updating!)
# VM version: JDK 1.8.0_151, VM 25.151-b12
# VM invoker: /usr/lib/jvm/java-racle/jre/bin/java
# VM options: <none>
# Warmup: 3 iterations, 1 s each
# Measurement: 10 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Average time, time/op
# Benchmark: ru.isalnikov.jmh.test.coin.CoinTest.test

# Run progress: 0,00% complete, ETA 00:00:13
# Fork: 1 of 1
# Warmup Iteration 1: 215,412 ms/op
# Warmup Iteration 2: 210,183 ms/op
# Warmup Iteration 3: 209,671 ms/op
Iteration 1: 215,331 ms/op
Iteration 2: 215,408 ms/op
Iteration 3: 206,632 ms/op
Iteration 4: 207,963 ms/op
Iteration 5: 206,663 ms/op
Iteration 6: 207,985 ms/op
Iteration 7: 208,378 ms/op
Iteration 8: 208,751 ms/op
Iteration 9: 209,564 ms/op
Iteration 10: 206,632 ms/op


Result "test":
209,331 ±(99.9%) 5,029 ms/op [Average]
(min, avg, max) = (206,632, 209,331, 215,408), stdev = 3,327
CI (99.9%): [204,301, 214,360] (assumes normal distribution)


# Run complete. Total time: 00:00:14

Benchmark Mode Cnt Score Error Units
CoinTest.test avgt 10 209,331 ± 5,029 ms/op
22 дек 17, 20:08    [21056196]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9005
Atum1
Монету бросают 8 раз. Найти вероятность того, что герб выпадет ровно 3 раза.
(Решение нужно через метод Монте Карло)
Скоростные показатели это хорошо.
Полученная вероятность соответствует формульной?
23 дек 17, 01:09    [21056856]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
MKZM
Member

Откуда:
Сообщений: 5135
А зачем это надо? На 2000 по скорости вряд ли почувствуете. Другие база.
23 дек 17, 01:26    [21056871]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 29 30 31 32 33 34 [35] 36 37 38   вперед  Ctrl
Все форумы / Java Ответить